1 /* Extended regular expression matching and search library,
3 (Implements POSIX draft P1003.2/D11.2, except for some of the
4 internationalization features.)
6 Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001,
7 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2, or (at your option)
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License along
20 with this program; if not, write to the Free Software Foundation,
21 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
23 /* AIX requires this to be the first thing in the file. */
24 #if defined _AIX && !defined REGEX_MALLOC
35 #ifndef INSIDE_RECURSION
39 # define WIDE_CHAR_SUPPORT (HAVE_WCTYPE_H && HAVE_WCHAR_H && HAVE_BTOWC)
41 /* For platform which support the ISO C amendement 1 functionality we
42 support user defined character classes. */
43 # if defined _LIBC || WIDE_CHAR_SUPPORT
44 /* Solaris 2.5 has a bug: <wchar.h> must be included before <wctype.h>. */
50 /* We have to keep the namespace clean. */
51 # define regfree(preg) __regfree (preg)
52 # define regexec(pr, st, nm, pm, ef) __regexec (pr, st, nm, pm, ef)
53 # define regcomp(preg, pattern, cflags) __regcomp (preg, pattern, cflags)
54 # define regerror(errcode, preg, errbuf, errbuf_size) \
55 __regerror(errcode, preg, errbuf, errbuf_size)
56 # define re_set_registers(bu, re, nu, st, en) \
57 __re_set_registers (bu, re, nu, st, en)
58 # define re_match_2(bufp, string1, size1, string2, size2, pos, regs, stop) \
59 __re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
60 # define re_match(bufp, string, size, pos, regs) \
61 __re_match (bufp, string, size, pos, regs)
62 # define re_search(bufp, string, size, startpos, range, regs) \
63 __re_search (bufp, string, size, startpos, range, regs)
64 # define re_compile_pattern(pattern, length, bufp) \
65 __re_compile_pattern (pattern, length, bufp)
66 # define re_set_syntax(syntax) __re_set_syntax (syntax)
67 # define re_search_2(bufp, st1, s1, st2, s2, startpos, range, regs, stop) \
68 __re_search_2 (bufp, st1, s1, st2, s2, startpos, range, regs, stop)
69 # define re_compile_fastmap(bufp) __re_compile_fastmap (bufp)
71 # define btowc __btowc
72 # define iswctype __iswctype
73 # define mbrtowc __mbrtowc
74 # define wcslen __wcslen
75 # define wcscoll __wcscoll
76 # define wcrtomb __wcrtomb
78 /* We are also using some library internals. */
79 # include <locale/localeinfo.h>
80 # include <locale/elem-hash.h>
81 # include <langinfo.h>
82 # include <locale/coll-lookup.h>
88 # define gettext(msgid) __dcgettext ("libc", msgid, LC_MESSAGES)
89 /* This define is so xgettext can find the internationalizable strings. */
90 # define gettext_noop(msgid) msgid
92 /* This is for other GNU distributions with internationalized messages. */
96 /* Support for bounded pointers. */
97 # if !defined _LIBC && !defined __BOUNDED_POINTERS__
98 # define __bounded /* nothing */
99 # define __unbounded /* nothing */
100 # define __ptrvalue /* nothing */
103 /* The `emacs' switch turns on certain matching commands
104 that make sense only in Emacs. */
111 # else /* not emacs */
113 /* If we are not linking with Emacs proper,
114 we can't use the relocating allocator
115 even if config.h says that we can. */
120 /* When used in Emacs's lib-src, we need to get bzero and bcopy somehow.
121 If nothing else has been done, use the method below. */
122 # ifdef INHIBIT_STRING_HEADER
123 # if !(defined HAVE_BZERO && defined HAVE_BCOPY)
124 # if !defined bzero && !defined bcopy
125 # undef INHIBIT_STRING_HEADER
130 /* This is the normal way of making sure we have a bcopy and a bzero.
131 This is used in most programs--a few other programs avoid this
132 by defining INHIBIT_STRING_HEADER. */
133 # ifndef INHIBIT_STRING_HEADER
137 # define bzero(s, n) (memset (s, '\0', n), (s))
139 # define bzero(s, n) __bzero (s, n)
144 /* Define the syntax stuff for \<, \>, etc. */
146 /* This must be nonzero for the wordchar and notwordchar pattern
147 commands in re_match_2. */
152 # ifdef SWITCH_ENUM_BUG
153 # define SWITCH_ENUM_CAST(x) ((int)(x))
155 # define SWITCH_ENUM_CAST(x) (x)
158 # endif /* not emacs */
163 # define MB_LEN_MAX 1
166 /* Get the interface, including the syntax bits. */
169 /* isalpha etc. are used for the character classes. */
172 /* Jim Meyering writes:
174 "... Some ctype macros are valid only for character codes that
175 isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
176 using /bin/cc or gcc but without giving an ansi option). So, all
177 ctype uses should be through macros like ISPRINT... If
178 STDC_HEADERS is defined, then autoconf has verified that the ctype
179 macros don't need to be guarded with references to isascii. ...
180 Defining isascii to 1 should let any compiler worth its salt
181 eliminate the && through constant folding."
182 Solaris defines some of these symbols so we must undefine them first. */
184 # if defined STDC_HEADERS || (!defined isascii && !defined HAVE_ISASCII)
185 # define IN_CTYPE_DOMAIN(c) 1
187 # define IN_CTYPE_DOMAIN(c) isascii(c)
191 # define ISBLANK(c) (IN_CTYPE_DOMAIN (c) && isblank (c))
193 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
196 # define ISGRAPH(c) (IN_CTYPE_DOMAIN (c) && isgraph (c))
198 # define ISGRAPH(c) (IN_CTYPE_DOMAIN (c) && isprint (c) && !isspace (c))
202 # define ISPRINT(c) (IN_CTYPE_DOMAIN (c) && isprint (c))
203 # define ISDIGIT(c) (IN_CTYPE_DOMAIN (c) && isdigit (c))
204 # define ISALNUM(c) (IN_CTYPE_DOMAIN (c) && isalnum (c))
205 # define ISALPHA(c) (IN_CTYPE_DOMAIN (c) && isalpha (c))
206 # define ISCNTRL(c) (IN_CTYPE_DOMAIN (c) && iscntrl (c))
207 # define ISLOWER(c) (IN_CTYPE_DOMAIN (c) && islower (c))
208 # define ISPUNCT(c) (IN_CTYPE_DOMAIN (c) && ispunct (c))
209 # define ISSPACE(c) (IN_CTYPE_DOMAIN (c) && isspace (c))
210 # define ISUPPER(c) (IN_CTYPE_DOMAIN (c) && isupper (c))
211 # define ISXDIGIT(c) (IN_CTYPE_DOMAIN (c) && isxdigit (c))
214 # define TOLOWER(c) _tolower(c)
216 # define TOLOWER(c) tolower(c)
220 /* How many characters in the character set. */
221 # define CHAR_SET_SIZE 256
225 extern char *re_syntax_table;
227 # else /* not SYNTAX_TABLE */
229 static char re_syntax_table[CHAR_SET_SIZE];
232 init_syntax_once (void)
239 bzero (re_syntax_table, sizeof re_syntax_table);
241 for (c = 0; c < CHAR_SET_SIZE; ++c)
243 re_syntax_table[c] = Sword;
245 re_syntax_table['_'] = Sword;
250 # endif /* not SYNTAX_TABLE */
252 # define SYNTAX(c) re_syntax_table[(unsigned char) (c)]
256 /* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
257 use `alloca' instead of `malloc'. This is because using malloc in
258 re_search* or re_match* could cause memory leaks when C-g is used in
259 Emacs; also, malloc is slower and causes storage fragmentation. On
260 the other hand, malloc is more portable, and easier to debug.
262 Because we sometimes use alloca, some routines have to be macros,
263 not functions -- `alloca'-allocated space disappears at the end of the
264 function it is called in. */
268 # define REGEX_ALLOCATE malloc
269 # define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
270 # define REGEX_FREE free
272 # else /* not REGEX_MALLOC */
274 /* Emacs already defines alloca, sometimes. */
277 /* Make alloca work the best possible way. */
280 # endif /* not alloca */
282 # define REGEX_ALLOCATE alloca
284 /* Assumes a `char *destination' variable. */
285 # define REGEX_REALLOCATE(source, osize, nsize) \
286 (destination = (char *) alloca (nsize), \
287 memcpy (destination, source, osize))
289 /* No need to do anything to free, after alloca. */
290 # define REGEX_FREE(arg) ((void)0) /* Do nothing! But inhibit gcc warning. */
292 # endif /* not REGEX_MALLOC */
294 /* Define how to allocate the failure stack. */
296 # if defined REL_ALLOC && defined REGEX_MALLOC
298 # define REGEX_ALLOCATE_STACK(size) \
299 r_alloc (&failure_stack_ptr, (size))
300 # define REGEX_REALLOCATE_STACK(source, osize, nsize) \
301 r_re_alloc (&failure_stack_ptr, (nsize))
302 # define REGEX_FREE_STACK(ptr) \
303 r_alloc_free (&failure_stack_ptr)
305 # else /* not using relocating allocator */
309 # define REGEX_ALLOCATE_STACK malloc
310 # define REGEX_REALLOCATE_STACK(source, osize, nsize) realloc (source, nsize)
311 # define REGEX_FREE_STACK free
313 # else /* not REGEX_MALLOC */
315 # define REGEX_ALLOCATE_STACK alloca
317 # define REGEX_REALLOCATE_STACK(source, osize, nsize) \
318 REGEX_REALLOCATE (source, osize, nsize)
319 /* No need to explicitly free anything. */
320 # define REGEX_FREE_STACK(arg)
322 # endif /* not REGEX_MALLOC */
323 # endif /* not using relocating allocator */
326 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
327 `string1' or just past its end. This works if PTR is NULL, which is
329 # define FIRST_STRING_P(ptr) \
330 (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
332 /* (Re)Allocate N items of type T using malloc, or fail. */
333 # define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
334 # define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
335 # define RETALLOC_IF(addr, n, t) \
336 if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
337 # define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
339 # define BYTEWIDTH 8 /* In bits. */
341 # define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
345 # define MAX(a, b) ((a) > (b) ? (a) : (b))
346 # define MIN(a, b) ((a) < (b) ? (a) : (b))
348 typedef char boolean;
352 static reg_errcode_t byte_regex_compile (const char *pattern, size_t size,
354 struct re_pattern_buffer *bufp);
356 static int byte_re_match_2_internal (struct re_pattern_buffer *bufp,
357 const char *string1, int size1,
358 const char *string2, int size2,
360 struct re_registers *regs,
362 static int byte_re_search_2 (struct re_pattern_buffer *bufp,
363 const char *string1, int size1,
364 const char *string2, int size2,
365 int startpos, int range,
366 struct re_registers *regs, int stop);
367 static int byte_re_compile_fastmap (struct re_pattern_buffer *bufp);
370 static reg_errcode_t wcs_regex_compile (const char *pattern, size_t size,
372 struct re_pattern_buffer *bufp);
375 static int wcs_re_match_2_internal (struct re_pattern_buffer *bufp,
376 const char *cstring1, int csize1,
377 const char *cstring2, int csize2,
379 struct re_registers *regs,
381 wchar_t *string1, int size1,
382 wchar_t *string2, int size2,
383 int *mbs_offset1, int *mbs_offset2);
384 static int wcs_re_search_2 (struct re_pattern_buffer *bufp,
385 const char *string1, int size1,
386 const char *string2, int size2,
387 int startpos, int range,
388 struct re_registers *regs, int stop);
389 static int wcs_re_compile_fastmap (struct re_pattern_buffer *bufp);
392 /* These are the command codes that appear in compiled regular
393 expressions. Some opcodes are followed by argument bytes. A
394 command code can specify any interpretation whatsoever for its
395 arguments. Zero bytes may appear in the compiled regular expression. */
401 /* Succeed right away--no more backtracking. */
404 /* Followed by one byte giving n, then by n literal bytes. */
408 /* Same as exactn, but contains binary data. */
412 /* Matches any (more or less) character. */
415 /* Matches any one char belonging to specified set. First
416 following byte is number of bitmap bytes. Then come bytes
417 for a bitmap saying which chars are in. Bits in each byte
418 are ordered low-bit-first. A character is in the set if its
419 bit is 1. A character too large to have a bit in the map is
420 automatically not in the set. */
421 /* ifdef MBS_SUPPORT, following element is length of character
422 classes, length of collating symbols, length of equivalence
423 classes, length of character ranges, and length of characters.
424 Next, character class element, collating symbols elements,
425 equivalence class elements, range elements, and character
427 See regex_compile function. */
430 /* Same parameters as charset, but match any character that is
431 not one of those specified. */
434 /* Start remembering the text that is matched, for storing in a
435 register. Followed by one byte with the register number, in
436 the range 0 to one less than the pattern buffer's re_nsub
437 field. Then followed by one byte with the number of groups
438 inner to this one. (This last has to be part of the
439 start_memory only because we need it in the on_failure_jump
443 /* Stop remembering the text that is matched and store it in a
444 memory register. Followed by one byte with the register
445 number, in the range 0 to one less than `re_nsub' in the
446 pattern buffer, and one byte with the number of inner groups,
447 just like `start_memory'. (We need the number of inner
448 groups here because we don't have any easy way of finding the
449 corresponding start_memory when we're at a stop_memory.) */
452 /* Match a duplicate of something remembered. Followed by one
453 byte containing the register number. */
456 /* Fail unless at beginning of line. */
459 /* Fail unless at end of line. */
462 /* Succeeds if at beginning of buffer (if emacs) or at beginning
463 of string to be matched (if not). */
466 /* Analogously, for end of buffer/string. */
469 /* Followed by two byte relative address to which to jump. */
472 /* Same as jump, but marks the end of an alternative. */
475 /* Followed by two-byte relative address of place to resume at
476 in case of failure. */
477 /* ifdef MBS_SUPPORT, the size of address is 1. */
480 /* Like on_failure_jump, but pushes a placeholder instead of the
481 current string position when executed. */
482 on_failure_keep_string_jump,
484 /* Throw away latest failure point and then jump to following
485 two-byte relative address. */
486 /* ifdef MBS_SUPPORT, the size of address is 1. */
489 /* Change to pop_failure_jump if know won't have to backtrack to
490 match; otherwise change to jump. This is used to jump
491 back to the beginning of a repeat. If what follows this jump
492 clearly won't match what the repeat does, such that we can be
493 sure that there is no use backtracking out of repetitions
494 already matched, then we change it to a pop_failure_jump.
495 Followed by two-byte address. */
496 /* ifdef MBS_SUPPORT, the size of address is 1. */
499 /* Jump to following two-byte address, and push a dummy failure
500 point. This failure point will be thrown away if an attempt
501 is made to use it for a failure. A `+' construct makes this
502 before the first repeat. Also used as an intermediary kind
503 of jump when compiling an alternative. */
504 /* ifdef MBS_SUPPORT, the size of address is 1. */
507 /* Push a dummy failure point and continue. Used at the end of
511 /* Followed by two-byte relative address and two-byte number n.
512 After matching N times, jump to the address upon failure. */
513 /* ifdef MBS_SUPPORT, the size of address is 1. */
516 /* Followed by two-byte relative address, and two-byte number n.
517 Jump to the address N times, then fail. */
518 /* ifdef MBS_SUPPORT, the size of address is 1. */
521 /* Set the following two-byte relative address to the
522 subsequent two-byte number. The address *includes* the two
524 /* ifdef MBS_SUPPORT, the size of address is 1. */
527 wordchar, /* Matches any word-constituent character. */
528 notwordchar, /* Matches any char that is not a word-constituent. */
530 wordbeg, /* Succeeds if at word beginning. */
531 wordend, /* Succeeds if at word end. */
533 wordbound, /* Succeeds if at a word boundary. */
534 notwordbound /* Succeeds if not at a word boundary. */
537 ,before_dot, /* Succeeds if before point. */
538 at_dot, /* Succeeds if at point. */
539 after_dot, /* Succeeds if after point. */
541 /* Matches any character whose syntax is specified. Followed by
542 a byte which contains a syntax code, e.g., Sword. */
545 /* Matches any character whose syntax is not that specified. */
549 #endif /* not INSIDE_RECURSION */
554 # define UCHAR_T unsigned char
555 # define COMPILED_BUFFER_VAR bufp->buffer
556 # define OFFSET_ADDRESS_SIZE 2
557 # define PREFIX(name) byte_##name
558 # define ARG_PREFIX(name) name
559 # define PUT_CHAR(c) putchar (c)
562 # define CHAR_T wchar_t
563 # define UCHAR_T wchar_t
564 # define COMPILED_BUFFER_VAR wc_buffer
565 # define OFFSET_ADDRESS_SIZE 1 /* the size which STORE_NUMBER macro use */
566 # define CHAR_CLASS_SIZE ((__alignof__(wctype_t)+sizeof(wctype_t))/sizeof(CHAR_T)+1)
567 # define PREFIX(name) wcs_##name
568 # define ARG_PREFIX(name) c##name
569 /* Should we use wide stream?? */
570 # define PUT_CHAR(c) printf ("%C", c);
576 # define INSIDE_RECURSION
578 # undef INSIDE_RECURSION
581 # define INSIDE_RECURSION
583 # undef INSIDE_RECURSION
588 # include "unlocked-io.h"
591 #ifdef INSIDE_RECURSION
592 /* Common operations on the compiled pattern. */
594 /* Store NUMBER in two contiguous bytes starting at DESTINATION. */
595 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
598 # define STORE_NUMBER(destination, number) \
600 *(destination) = (UCHAR_T)(number); \
603 # define STORE_NUMBER(destination, number) \
605 (destination)[0] = (number) & 0377; \
606 (destination)[1] = (number) >> 8; \
610 /* Same as STORE_NUMBER, except increment DESTINATION to
611 the byte after where the number is stored. Therefore, DESTINATION
612 must be an lvalue. */
613 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
615 # define STORE_NUMBER_AND_INCR(destination, number) \
617 STORE_NUMBER (destination, number); \
618 (destination) += OFFSET_ADDRESS_SIZE; \
621 /* Put into DESTINATION a number stored in two contiguous bytes starting
623 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
626 # define EXTRACT_NUMBER(destination, source) \
628 (destination) = *(source); \
631 # define EXTRACT_NUMBER(destination, source) \
633 (destination) = *(source) & 0377; \
634 (destination) += (signed char) (*((source) + 1)) << 8; \
640 PREFIX(extract_number) (int *dest, UCHAR_T *source)
645 signed char temp = source[1];
646 *dest = *source & 0377;
651 # ifndef EXTRACT_MACROS /* To debug the macros. */
652 # undef EXTRACT_NUMBER
653 # define EXTRACT_NUMBER(dest, src) PREFIX(extract_number) (&dest, src)
654 # endif /* not EXTRACT_MACROS */
658 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
659 SOURCE must be an lvalue. */
661 # define EXTRACT_NUMBER_AND_INCR(destination, source) \
663 EXTRACT_NUMBER (destination, source); \
664 (source) += OFFSET_ADDRESS_SIZE; \
669 PREFIX(extract_number_and_incr) (int *destination, UCHAR_T **source)
671 PREFIX(extract_number) (destination, *source);
672 *source += OFFSET_ADDRESS_SIZE;
675 # ifndef EXTRACT_MACROS
676 # undef EXTRACT_NUMBER_AND_INCR
677 # define EXTRACT_NUMBER_AND_INCR(dest, src) \
678 PREFIX(extract_number_and_incr) (&dest, &src)
679 # endif /* not EXTRACT_MACROS */
685 /* If DEBUG is defined, Regex prints many voluminous messages about what
686 it is doing (if the variable `debug' is nonzero). If linked with the
687 main program in `iregex.c', you can enter patterns and strings
688 interactively. And if linked with the main program in `main.c' and
689 the other test files, you can run the already-written tests. */
693 # ifndef DEFINED_ONCE
695 /* We use standard I/O for debugging. */
698 /* It is useful to test things that ``must'' be true when debugging. */
703 # define DEBUG_STATEMENT(e) e
704 # define DEBUG_PRINT1(x) if (debug) printf (x)
705 # define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
706 # define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
707 # define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
708 # endif /* not DEFINED_ONCE */
710 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \
711 if (debug) PREFIX(print_partial_compiled_pattern) (s, e)
712 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \
713 if (debug) PREFIX(print_double_string) (w, s1, sz1, s2, sz2)
716 /* Print the fastmap in human-readable form. */
718 # ifndef DEFINED_ONCE
720 print_fastmap (char *fastmap)
722 unsigned was_a_range = 0;
725 while (i < (1 << BYTEWIDTH))
731 while (i < (1 << BYTEWIDTH) && fastmap[i])
745 # endif /* not DEFINED_ONCE */
748 /* Print a compiled pattern string in human-readable form, starting at
749 the START pointer into it and ending just before the pointer END. */
752 PREFIX(print_partial_compiled_pattern) (UCHAR_T *start, UCHAR_T *end)
765 /* Loop over pattern commands. */
769 printf ("%td:\t", p - start);
771 printf ("%ld:\t", (long int) (p - start));
774 switch ((re_opcode_t) *p++)
782 printf ("/exactn/%d", mcnt);
794 printf ("/exactn_bin/%d", mcnt);
797 printf("/%lx", (long int) *p++);
801 # endif /* MBS_SUPPORT */
805 printf ("/start_memory/%d/%ld", mcnt, (long int) *p++);
810 printf ("/stop_memory/%d/%ld", mcnt, (long int) *p++);
814 printf ("/duplicate/%ld", (long int) *p++);
827 printf ("/charset [%s",
828 (re_opcode_t) *(workp - 1) == charset_not ? "^" : "");
830 length = *workp++; /* the length of char_classes */
831 for (i=0 ; i<length ; i++)
832 printf("[:%lx:]", (long int) *p++);
833 length = *workp++; /* the length of collating_symbol */
834 for (i=0 ; i<length ;)
838 PUT_CHAR((i++,*p++));
842 length = *workp++; /* the length of equivalence_class */
843 for (i=0 ; i<length ;)
847 PUT_CHAR((i++,*p++));
851 length = *workp++; /* the length of char_range */
852 for (i=0 ; i<length ; i++)
854 wchar_t range_start = *p++;
855 wchar_t range_end = *p++;
856 printf("%C-%C", range_start, range_end);
858 length = *workp++; /* the length of char */
859 for (i=0 ; i<length ; i++)
863 register int c, last = -100;
864 register int in_range = 0;
866 printf ("/charset [%s",
867 (re_opcode_t) *(p - 1) == charset_not ? "^" : "");
869 assert (p + *p < pend);
871 for (c = 0; c < 256; c++)
873 && (p[1 + (c/8)] & (1 << (c % 8))))
875 /* Are we starting a range? */
876 if (last + 1 == c && ! in_range)
881 /* Have we broken a range? */
882 else if (last + 1 != c && in_range)
912 case on_failure_jump:
913 PREFIX(extract_number_and_incr) (&mcnt, &p);
915 printf ("/on_failure_jump to %td", p + mcnt - start);
917 printf ("/on_failure_jump to %ld", (long int) (p + mcnt - start));
921 case on_failure_keep_string_jump:
922 PREFIX(extract_number_and_incr) (&mcnt, &p);
924 printf ("/on_failure_keep_string_jump to %td", p + mcnt - start);
926 printf ("/on_failure_keep_string_jump to %ld",
927 (long int) (p + mcnt - start));
931 case dummy_failure_jump:
932 PREFIX(extract_number_and_incr) (&mcnt, &p);
934 printf ("/dummy_failure_jump to %td", p + mcnt - start);
936 printf ("/dummy_failure_jump to %ld", (long int) (p + mcnt - start));
940 case push_dummy_failure:
941 printf ("/push_dummy_failure");
945 PREFIX(extract_number_and_incr) (&mcnt, &p);
947 printf ("/maybe_pop_jump to %td", p + mcnt - start);
949 printf ("/maybe_pop_jump to %ld", (long int) (p + mcnt - start));
953 case pop_failure_jump:
954 PREFIX(extract_number_and_incr) (&mcnt, &p);
956 printf ("/pop_failure_jump to %td", p + mcnt - start);
958 printf ("/pop_failure_jump to %ld", (long int) (p + mcnt - start));
963 PREFIX(extract_number_and_incr) (&mcnt, &p);
965 printf ("/jump_past_alt to %td", p + mcnt - start);
967 printf ("/jump_past_alt to %ld", (long int) (p + mcnt - start));
972 PREFIX(extract_number_and_incr) (&mcnt, &p);
974 printf ("/jump to %td", p + mcnt - start);
976 printf ("/jump to %ld", (long int) (p + mcnt - start));
981 PREFIX(extract_number_and_incr) (&mcnt, &p);
983 PREFIX(extract_number_and_incr) (&mcnt2, &p);
985 printf ("/succeed_n to %td, %d times", p1 - start, mcnt2);
987 printf ("/succeed_n to %ld, %d times",
988 (long int) (p1 - start), mcnt2);
993 PREFIX(extract_number_and_incr) (&mcnt, &p);
995 PREFIX(extract_number_and_incr) (&mcnt2, &p);
996 printf ("/jump_n to %d, %d times", p1 - start, mcnt2);
1000 PREFIX(extract_number_and_incr) (&mcnt, &p);
1002 PREFIX(extract_number_and_incr) (&mcnt2, &p);
1004 printf ("/set_number_at location %td to %d", p1 - start, mcnt2);
1006 printf ("/set_number_at location %ld to %d",
1007 (long int) (p1 - start), mcnt2);
1012 printf ("/wordbound");
1016 printf ("/notwordbound");
1020 printf ("/wordbeg");
1024 printf ("/wordend");
1029 printf ("/before_dot");
1037 printf ("/after_dot");
1041 printf ("/syntaxspec");
1043 printf ("/%d", mcnt);
1047 printf ("/notsyntaxspec");
1049 printf ("/%d", mcnt);
1054 printf ("/wordchar");
1058 printf ("/notwordchar");
1070 printf ("?%ld", (long int) *(p-1));
1077 printf ("%td:\tend of pattern.\n", p - start);
1079 printf ("%ld:\tend of pattern.\n", (long int) (p - start));
1085 PREFIX(print_compiled_pattern) (struct re_pattern_buffer *bufp)
1087 UCHAR_T *buffer = (UCHAR_T*) bufp->buffer;
1089 PREFIX(print_partial_compiled_pattern) (buffer, buffer
1090 + bufp->used / sizeof(UCHAR_T));
1091 printf ("%ld bytes used/%ld bytes allocated.\n",
1092 bufp->used, bufp->allocated);
1094 if (bufp->fastmap_accurate && bufp->fastmap)
1096 printf ("fastmap: ");
1097 print_fastmap (bufp->fastmap);
1101 printf ("re_nsub: %Zd\t", bufp->re_nsub);
1103 printf ("re_nsub: %ld\t", (long int) bufp->re_nsub);
1105 printf ("regs_alloc: %d\t", bufp->regs_allocated);
1106 printf ("can_be_null: %d\t", bufp->can_be_null);
1107 printf ("newline_anchor: %d\n", bufp->newline_anchor);
1108 printf ("no_sub: %d\t", bufp->no_sub);
1109 printf ("not_bol: %d\t", bufp->not_bol);
1110 printf ("not_eol: %d\t", bufp->not_eol);
1111 printf ("syntax: %lx\n", bufp->syntax);
1112 /* Perhaps we should print the translate table? */
1117 PREFIX(print_double_string) (const CHAR_T *where,
1118 const CHAR_T *string1,
1119 const CHAR_T *string2,
1131 if (FIRST_STRING_P (where))
1133 for (this_char = where - string1; this_char < size1; this_char++)
1134 PUT_CHAR (string1[this_char]);
1140 for (this_char = where - string2; this_char < size2; this_char++)
1142 PUT_CHAR (string2[this_char]);
1145 fputs ("...", stdout);
1152 # ifndef DEFINED_ONCE
1161 # else /* not DEBUG */
1163 # ifndef DEFINED_ONCE
1167 # define DEBUG_STATEMENT(e)
1168 # define DEBUG_PRINT1(x)
1169 # define DEBUG_PRINT2(x1, x2)
1170 # define DEBUG_PRINT3(x1, x2, x3)
1171 # define DEBUG_PRINT4(x1, x2, x3, x4)
1172 # endif /* not DEFINED_ONCE */
1173 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
1174 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
1176 # endif /* not DEBUG */
1181 /* This convert a multibyte string to a wide character string.
1182 And write their correspondances to offset_buffer(see below)
1183 and write whether each wchar_t is binary data to is_binary.
1184 This assume invalid multibyte sequences as binary data.
1185 We assume offset_buffer and is_binary is already allocated
1189 convert_mbs_to_wcs (CHAR_T *dest,
1190 const unsigned char* src,
1192 /* The length of multibyte string. */
1195 /* Correspondences between src(char string) and
1196 dest(wchar_t string) for optimization. E.g.:
1198 dest = {'X', 'Y', 'Z'}
1199 (each "xxx", "y" and "zz" represent one
1200 multibyte character corresponding to 'X',
1202 offset_buffer = {0, 0+3("xxx"), 0+3+1("y"),
1209 wchar_t *pdest = dest;
1210 const unsigned char *psrc = src;
1211 size_t wc_count = 0;
1215 size_t mb_remain = len;
1216 size_t mb_count = 0;
1218 /* Initialize the conversion state. */
1219 memset (&mbs, 0, sizeof (mbstate_t));
1221 offset_buffer[0] = 0;
1222 for( ; mb_remain > 0 ; ++wc_count, ++pdest, mb_remain -= consumed,
1225 consumed = mbrtowc (pdest, psrc, mb_remain, &mbs);
1228 /* failed to convert. maybe src contains binary data.
1229 So we consume 1 byte manualy. */
1233 is_binary[wc_count] = TRUE;
1236 is_binary[wc_count] = FALSE;
1237 /* In sjis encoding, we use yen sign as escape character in
1238 place of reverse solidus. So we convert 0x5c(yen sign in
1239 sjis) to not 0xa5(yen sign in UCS2) but 0x5c(reverse
1240 solidus in UCS2). */
1241 if (consumed == 1 && (int) *psrc == 0x5c && (int) *pdest == 0xa5)
1242 *pdest = (wchar_t) *psrc;
1244 offset_buffer[wc_count + 1] = mb_count += consumed;
1247 /* Fill remain of the buffer with sentinel. */
1248 for (i = wc_count + 1 ; i <= len ; i++)
1249 offset_buffer[i] = mb_count + 1;
1256 #else /* not INSIDE_RECURSION */
1258 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
1259 also be assigned to arbitrarily: each pattern buffer stores its own
1260 syntax, so it can be changed between regex compilations. */
1261 /* This has no initializer because initialized variables in Emacs
1262 become read-only after dumping. */
1263 reg_syntax_t re_syntax_options;
1266 /* Specify the precise syntax of regexps for compilation. This provides
1267 for compatibility for various utilities which historically have
1268 different, incompatible syntaxes.
1270 The argument SYNTAX is a bit mask comprised of the various bits
1271 defined in regex.h. We return the old syntax. */
1274 re_set_syntax (reg_syntax_t syntax)
1276 reg_syntax_t ret = re_syntax_options;
1278 re_syntax_options = syntax;
1280 if (syntax & RE_DEBUG)
1282 else if (debug) /* was on but now is not */
1288 weak_alias (__re_set_syntax, re_set_syntax)
1291 /* This table gives an error message for each of the error codes listed
1292 in regex.h. Obviously the order here has to be same as there.
1293 POSIX doesn't require that we do anything for REG_NOERROR,
1294 but why not be nice? */
1296 static const char re_error_msgid[] =
1298 # define REG_NOERROR_IDX 0
1299 gettext_noop ("Success") /* REG_NOERROR */
1301 # define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
1302 gettext_noop ("No match") /* REG_NOMATCH */
1304 # define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
1305 gettext_noop ("Invalid regular expression") /* REG_BADPAT */
1307 # define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
1308 gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
1310 # define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
1311 gettext_noop ("Invalid character class name") /* REG_ECTYPE */
1313 # define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
1314 gettext_noop ("Trailing backslash") /* REG_EESCAPE */
1316 # define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
1317 gettext_noop ("Invalid back reference") /* REG_ESUBREG */
1319 # define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
1320 gettext_noop ("Unmatched [ or [^") /* REG_EBRACK */
1322 # define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
1323 gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
1325 # define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
1326 gettext_noop ("Unmatched \\{") /* REG_EBRACE */
1328 # define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")
1329 gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
1331 # define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
1332 gettext_noop ("Invalid range end") /* REG_ERANGE */
1334 # define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
1335 gettext_noop ("Memory exhausted") /* REG_ESPACE */
1337 # define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
1338 gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
1340 # define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
1341 gettext_noop ("Premature end of regular expression") /* REG_EEND */
1343 # define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")
1344 gettext_noop ("Regular expression too big") /* REG_ESIZE */
1346 # define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
1347 gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
1350 static const size_t re_error_msgid_idx[] =
1371 #endif /* INSIDE_RECURSION */
1373 #ifndef DEFINED_ONCE
1374 /* Avoiding alloca during matching, to placate r_alloc. */
1376 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
1377 searching and matching functions should not call alloca. On some
1378 systems, alloca is implemented in terms of malloc, and if we're
1379 using the relocating allocator routines, then malloc could cause a
1380 relocation, which might (if the strings being searched are in the
1381 ralloc heap) shift the data out from underneath the regexp
1384 Here's another reason to avoid allocation: Emacs
1385 processes input from X in a signal handler; processing X input may
1386 call malloc; if input arrives while a matching routine is calling
1387 malloc, then we're scrod. But Emacs can't just block input while
1388 calling matching routines; then we don't notice interrupts when
1389 they come in. So, Emacs blocks input around all regexp calls
1390 except the matching calls, which it leaves unprotected, in the
1391 faith that they will not malloc. */
1393 /* Normally, this is fine. */
1394 # define MATCH_MAY_ALLOCATE
1396 /* When using GNU C, we are not REALLY using the C alloca, no matter
1397 what config.h may say. So don't take precautions for it. */
1402 /* The match routines may not allocate if (1) they would do it with malloc
1403 and (2) it's not safe for them to use malloc.
1404 Note that if REL_ALLOC is defined, matching would not use malloc for the
1405 failure stack, but we would still use it for the register vectors;
1406 so REL_ALLOC should not affect this. */
1407 # if (defined C_ALLOCA || defined REGEX_MALLOC) && defined emacs
1408 # undef MATCH_MAY_ALLOCATE
1410 #endif /* not DEFINED_ONCE */
1412 #ifdef INSIDE_RECURSION
1413 /* Failure stack declarations and macros; both re_compile_fastmap and
1414 re_match_2 use a failure stack. These have to be macros because of
1415 REGEX_ALLOCATE_STACK. */
1418 /* Number of failure points for which to initially allocate space
1419 when matching. If this number is exceeded, we allocate more
1420 space, so it is not a hard limit. */
1421 # ifndef INIT_FAILURE_ALLOC
1422 # define INIT_FAILURE_ALLOC 5
1425 /* Roughly the maximum number of failure points on the stack. Would be
1426 exactly that if always used MAX_FAILURE_ITEMS items each time we failed.
1427 This is a variable only so users of regex can assign to it; we never
1428 change it ourselves. */
1430 # ifdef INT_IS_16BIT
1432 # ifndef DEFINED_ONCE
1433 # if defined MATCH_MAY_ALLOCATE
1434 /* 4400 was enough to cause a crash on Alpha OSF/1,
1435 whose default stack limit is 2mb. */
1436 long int re_max_failures = 4000;
1438 long int re_max_failures = 2000;
1442 union PREFIX(fail_stack_elt)
1448 typedef union PREFIX(fail_stack_elt) PREFIX(fail_stack_elt_t);
1452 PREFIX(fail_stack_elt_t) *stack;
1453 unsigned long int size;
1454 unsigned long int avail; /* Offset of next open position. */
1455 } PREFIX(fail_stack_type);
1457 # else /* not INT_IS_16BIT */
1459 # ifndef DEFINED_ONCE
1460 # if defined MATCH_MAY_ALLOCATE
1461 /* 4400 was enough to cause a crash on Alpha OSF/1,
1462 whose default stack limit is 2mb. */
1463 int re_max_failures = 4000;
1465 int re_max_failures = 2000;
1469 union PREFIX(fail_stack_elt)
1475 typedef union PREFIX(fail_stack_elt) PREFIX(fail_stack_elt_t);
1479 PREFIX(fail_stack_elt_t) *stack;
1481 unsigned avail; /* Offset of next open position. */
1482 } PREFIX(fail_stack_type);
1484 # endif /* INT_IS_16BIT */
1486 # ifndef DEFINED_ONCE
1487 # define FAIL_STACK_EMPTY() (fail_stack.avail == 0)
1488 # define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
1489 # define FAIL_STACK_FULL() (fail_stack.avail == fail_stack.size)
1493 /* Define macros to initialize and free the failure stack.
1494 Do `return -2' if the alloc fails. */
1496 # ifdef MATCH_MAY_ALLOCATE
1497 # define INIT_FAIL_STACK() \
1499 fail_stack.stack = (PREFIX(fail_stack_elt_t) *) \
1500 REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * sizeof (PREFIX(fail_stack_elt_t))); \
1502 if (fail_stack.stack == NULL) \
1505 fail_stack.size = INIT_FAILURE_ALLOC; \
1506 fail_stack.avail = 0; \
1509 # define RESET_FAIL_STACK() REGEX_FREE_STACK (fail_stack.stack)
1511 # define INIT_FAIL_STACK() \
1513 fail_stack.avail = 0; \
1516 # define RESET_FAIL_STACK()
1520 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
1522 Return 1 if succeeds, and 0 if either ran out of memory
1523 allocating space for it or it was already too large.
1525 REGEX_REALLOCATE_STACK requires `destination' be declared. */
1527 # define DOUBLE_FAIL_STACK(fail_stack) \
1528 ((fail_stack).size > (unsigned) (re_max_failures * MAX_FAILURE_ITEMS) \
1530 : ((fail_stack).stack = (PREFIX(fail_stack_elt_t) *) \
1531 REGEX_REALLOCATE_STACK ((fail_stack).stack, \
1532 (fail_stack).size * sizeof (PREFIX(fail_stack_elt_t)), \
1533 ((fail_stack).size << 1) * sizeof (PREFIX(fail_stack_elt_t))),\
1535 (fail_stack).stack == NULL \
1537 : ((fail_stack).size <<= 1, \
1541 /* Push pointer POINTER on FAIL_STACK.
1542 Return 1 if was able to do so and 0 if ran out of memory allocating
1544 # define PUSH_PATTERN_OP(POINTER, FAIL_STACK) \
1545 ((FAIL_STACK_FULL () \
1546 && !DOUBLE_FAIL_STACK (FAIL_STACK)) \
1548 : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER, \
1551 /* Push a pointer value onto the failure stack.
1552 Assumes the variable `fail_stack'. Probably should only
1553 be called from within `PUSH_FAILURE_POINT'. */
1554 # define PUSH_FAILURE_POINTER(item) \
1555 fail_stack.stack[fail_stack.avail++].pointer = (UCHAR_T *) (item)
1557 /* This pushes an integer-valued item onto the failure stack.
1558 Assumes the variable `fail_stack'. Probably should only
1559 be called from within `PUSH_FAILURE_POINT'. */
1560 # define PUSH_FAILURE_INT(item) \
1561 fail_stack.stack[fail_stack.avail++].integer = (item)
1563 /* Push a fail_stack_elt_t value onto the failure stack.
1564 Assumes the variable `fail_stack'. Probably should only
1565 be called from within `PUSH_FAILURE_POINT'. */
1566 # define PUSH_FAILURE_ELT(item) \
1567 fail_stack.stack[fail_stack.avail++] = (item)
1569 /* These three POP... operations complement the three PUSH... operations.
1570 All assume that `fail_stack' is nonempty. */
1571 # define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1572 # define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1573 # define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
1575 /* Used to omit pushing failure point id's when we're not debugging. */
1577 # define DEBUG_PUSH PUSH_FAILURE_INT
1578 # define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT ()
1580 # define DEBUG_PUSH(item)
1581 # define DEBUG_POP(item_addr)
1585 /* Push the information about the state we will need
1586 if we ever fail back to it.
1588 Requires variables fail_stack, regstart, regend, reg_info, and
1589 num_regs_pushed be declared. DOUBLE_FAIL_STACK requires `destination'
1592 Does `return FAILURE_CODE' if runs out of memory. */
1594 # define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code) \
1596 char *destination; \
1597 /* Must be int, so when we don't save any registers, the arithmetic \
1598 of 0 + -1 isn't done as unsigned. */ \
1599 /* Can't be int, since there is not a shred of a guarantee that int \
1600 is wide enough to hold a value of something to which pointer can \
1602 active_reg_t this_reg; \
1604 DEBUG_STATEMENT (failure_id++); \
1605 DEBUG_STATEMENT (nfailure_points_pushed++); \
1606 DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id); \
1607 DEBUG_PRINT2 (" Before push, next avail: %d\n", (fail_stack).avail);\
1608 DEBUG_PRINT2 (" size: %d\n", (fail_stack).size);\
1610 DEBUG_PRINT2 (" slots needed: %ld\n", NUM_FAILURE_ITEMS); \
1611 DEBUG_PRINT2 (" available: %d\n", REMAINING_AVAIL_SLOTS); \
1613 /* Ensure we have enough space allocated for what we will push. */ \
1614 while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS) \
1616 if (!DOUBLE_FAIL_STACK (fail_stack)) \
1617 return failure_code; \
1619 DEBUG_PRINT2 ("\n Doubled stack; size now: %d\n", \
1620 (fail_stack).size); \
1621 DEBUG_PRINT2 (" slots available: %d\n", REMAINING_AVAIL_SLOTS);\
1624 /* Push the info, starting with the registers. */ \
1625 DEBUG_PRINT1 ("\n"); \
1628 for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
1631 DEBUG_PRINT2 (" Pushing reg: %lu\n", this_reg); \
1632 DEBUG_STATEMENT (num_regs_pushed++); \
1634 DEBUG_PRINT2 (" start: %p\n", regstart[this_reg]); \
1635 PUSH_FAILURE_POINTER (regstart[this_reg]); \
1637 DEBUG_PRINT2 (" end: %p\n", regend[this_reg]); \
1638 PUSH_FAILURE_POINTER (regend[this_reg]); \
1640 DEBUG_PRINT2 (" info: %p\n ", \
1641 reg_info[this_reg].word.pointer); \
1642 DEBUG_PRINT2 (" match_null=%d", \
1643 REG_MATCH_NULL_STRING_P (reg_info[this_reg])); \
1644 DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg])); \
1645 DEBUG_PRINT2 (" matched_something=%d", \
1646 MATCHED_SOMETHING (reg_info[this_reg])); \
1647 DEBUG_PRINT2 (" ever_matched=%d", \
1648 EVER_MATCHED_SOMETHING (reg_info[this_reg])); \
1649 DEBUG_PRINT1 ("\n"); \
1650 PUSH_FAILURE_ELT (reg_info[this_reg].word); \
1653 DEBUG_PRINT2 (" Pushing low active reg: %ld\n", lowest_active_reg);\
1654 PUSH_FAILURE_INT (lowest_active_reg); \
1656 DEBUG_PRINT2 (" Pushing high active reg: %ld\n", highest_active_reg);\
1657 PUSH_FAILURE_INT (highest_active_reg); \
1659 DEBUG_PRINT2 (" Pushing pattern %p:\n", pattern_place); \
1660 DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend); \
1661 PUSH_FAILURE_POINTER (pattern_place); \
1663 DEBUG_PRINT2 (" Pushing string %p: `", string_place); \
1664 DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, \
1666 DEBUG_PRINT1 ("'\n"); \
1667 PUSH_FAILURE_POINTER (string_place); \
1669 DEBUG_PRINT2 (" Pushing failure id: %u\n", failure_id); \
1670 DEBUG_PUSH (failure_id); \
1673 # ifndef DEFINED_ONCE
1674 /* This is the number of items that are pushed and popped on the stack
1675 for each register. */
1676 # define NUM_REG_ITEMS 3
1678 /* Individual items aside from the registers. */
1680 # define NUM_NONREG_ITEMS 5 /* Includes failure point id. */
1682 # define NUM_NONREG_ITEMS 4
1685 /* We push at most this many items on the stack. */
1686 /* We used to use (num_regs - 1), which is the number of registers
1687 this regexp will save; but that was changed to 5
1688 to avoid stack overflow for a regexp with lots of parens. */
1689 # define MAX_FAILURE_ITEMS (5 * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
1691 /* We actually push this many items. */
1692 # define NUM_FAILURE_ITEMS \
1694 ? 0 : highest_active_reg - lowest_active_reg + 1) \
1698 /* How many items can still be added to the stack without overflowing it. */
1699 # define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1700 # endif /* not DEFINED_ONCE */
1703 /* Pops what PUSH_FAIL_STACK pushes.
1705 We restore into the parameters, all of which should be lvalues:
1706 STR -- the saved data position.
1707 PAT -- the saved pattern position.
1708 LOW_REG, HIGH_REG -- the highest and lowest active registers.
1709 REGSTART, REGEND -- arrays of string positions.
1710 REG_INFO -- array of information about each subexpression.
1712 Also assumes the variables `fail_stack' and (if debugging), `bufp',
1713 `pend', `string1', `size1', `string2', and `size2'. */
1714 # define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
1716 DEBUG_STATEMENT (unsigned failure_id;) \
1717 active_reg_t this_reg; \
1718 const UCHAR_T *string_temp; \
1720 assert (!FAIL_STACK_EMPTY ()); \
1722 /* Remove failure points and point to how many regs pushed. */ \
1723 DEBUG_PRINT1 ("POP_FAILURE_POINT:\n"); \
1724 DEBUG_PRINT2 (" Before pop, next avail: %d\n", fail_stack.avail); \
1725 DEBUG_PRINT2 (" size: %d\n", fail_stack.size); \
1727 assert (fail_stack.avail >= NUM_NONREG_ITEMS); \
1729 DEBUG_POP (&failure_id); \
1730 DEBUG_PRINT2 (" Popping failure id: %u\n", failure_id); \
1732 /* If the saved string location is NULL, it came from an \
1733 on_failure_keep_string_jump opcode, and we want to throw away the \
1734 saved NULL, thus retaining our current position in the string. */ \
1735 string_temp = POP_FAILURE_POINTER (); \
1736 if (string_temp != NULL) \
1737 str = (const CHAR_T *) string_temp; \
1739 DEBUG_PRINT2 (" Popping string %p: `", str); \
1740 DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \
1741 DEBUG_PRINT1 ("'\n"); \
1743 pat = (UCHAR_T *) POP_FAILURE_POINTER (); \
1744 DEBUG_PRINT2 (" Popping pattern %p:\n", pat); \
1745 DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \
1747 /* Restore register info. */ \
1748 high_reg = (active_reg_t) POP_FAILURE_INT (); \
1749 DEBUG_PRINT2 (" Popping high active reg: %ld\n", high_reg); \
1751 low_reg = (active_reg_t) POP_FAILURE_INT (); \
1752 DEBUG_PRINT2 (" Popping low active reg: %ld\n", low_reg); \
1755 for (this_reg = high_reg; this_reg >= low_reg; this_reg--) \
1757 DEBUG_PRINT2 (" Popping reg: %ld\n", this_reg); \
1759 reg_info[this_reg].word = POP_FAILURE_ELT (); \
1760 DEBUG_PRINT2 (" info: %p\n", \
1761 reg_info[this_reg].word.pointer); \
1763 regend[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER (); \
1764 DEBUG_PRINT2 (" end: %p\n", regend[this_reg]); \
1766 regstart[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER (); \
1767 DEBUG_PRINT2 (" start: %p\n", regstart[this_reg]); \
1771 for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
1773 reg_info[this_reg].word.integer = 0; \
1774 regend[this_reg] = 0; \
1775 regstart[this_reg] = 0; \
1777 highest_active_reg = high_reg; \
1780 set_regs_matched_done = 0; \
1781 DEBUG_STATEMENT (nfailure_points_popped++); \
1782 } /* POP_FAILURE_POINT */
1784 /* Structure for per-register (a.k.a. per-group) information.
1785 Other register information, such as the
1786 starting and ending positions (which are addresses), and the list of
1787 inner groups (which is a bits list) are maintained in separate
1790 We are making a (strictly speaking) nonportable assumption here: that
1791 the compiler will pack our bit fields into something that fits into
1792 the type of `word', i.e., is something that fits into one item on the
1796 /* Declarations and macros for re_match_2. */
1800 PREFIX(fail_stack_elt_t) word;
1803 /* This field is one if this group can match the empty string,
1804 zero if not. If not yet determined, `MATCH_NULL_UNSET_VALUE'. */
1805 # define MATCH_NULL_UNSET_VALUE 3
1806 unsigned match_null_string_p : 2;
1807 unsigned is_active : 1;
1808 unsigned matched_something : 1;
1809 unsigned ever_matched_something : 1;
1811 } PREFIX(register_info_type);
1813 # ifndef DEFINED_ONCE
1814 # define REG_MATCH_NULL_STRING_P(R) ((R).bits.match_null_string_p)
1815 # define IS_ACTIVE(R) ((R).bits.is_active)
1816 # define MATCHED_SOMETHING(R) ((R).bits.matched_something)
1817 # define EVER_MATCHED_SOMETHING(R) ((R).bits.ever_matched_something)
1820 /* Call this when have matched a real character; it sets `matched' flags
1821 for the subexpressions which we are currently inside. Also records
1822 that those subexprs have matched. */
1823 # define SET_REGS_MATCHED() \
1826 if (!set_regs_matched_done) \
1829 set_regs_matched_done = 1; \
1830 for (r = lowest_active_reg; r <= highest_active_reg; r++) \
1832 MATCHED_SOMETHING (reg_info[r]) \
1833 = EVER_MATCHED_SOMETHING (reg_info[r]) \
1839 # endif /* not DEFINED_ONCE */
1841 /* Registers are set to a sentinel when they haven't yet matched. */
1842 static CHAR_T PREFIX(reg_unset_dummy);
1843 # define REG_UNSET_VALUE (&PREFIX(reg_unset_dummy))
1844 # define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
1846 /* Subroutine declarations and macros for regex_compile. */
1847 static void PREFIX(store_op1) (re_opcode_t op, UCHAR_T *loc, int arg);
1848 static void PREFIX(store_op2) (re_opcode_t op, UCHAR_T *loc,
1849 int arg1, int arg2);
1850 static void PREFIX(insert_op1) (re_opcode_t op, UCHAR_T *loc,
1851 int arg, UCHAR_T *end);
1852 static void PREFIX(insert_op2) (re_opcode_t op, UCHAR_T *loc,
1853 int arg1, int arg2, UCHAR_T *end);
1854 static boolean PREFIX(at_begline_loc_p) (const CHAR_T *pattern,
1856 reg_syntax_t syntax);
1857 static boolean PREFIX(at_endline_loc_p) (const CHAR_T *p,
1859 reg_syntax_t syntax);
1861 static reg_errcode_t wcs_compile_range (CHAR_T range_start,
1862 const CHAR_T **p_ptr,
1865 reg_syntax_t syntax,
1868 static void insert_space (int num, CHAR_T *loc, CHAR_T *end);
1870 static reg_errcode_t byte_compile_range (unsigned int range_start,
1874 reg_syntax_t syntax,
1878 /* Fetch the next character in the uncompiled pattern---translating it
1879 if necessary. Also cast from a signed character in the constant
1880 string passed to us by the user to an unsigned char that we can use
1881 as an array index (in, e.g., `translate'). */
1882 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1883 because it is impossible to allocate 4GB array for some encodings
1884 which have 4 byte character_set like UCS4. */
1887 # define PATFETCH(c) \
1888 do {if (p == pend) return REG_EEND; \
1889 c = (UCHAR_T) *p++; \
1890 if (translate && (c <= 0xff)) c = (UCHAR_T) translate[c]; \
1893 # define PATFETCH(c) \
1894 do {if (p == pend) return REG_EEND; \
1895 c = (unsigned char) *p++; \
1896 if (translate) c = (unsigned char) translate[c]; \
1901 /* Fetch the next character in the uncompiled pattern, with no
1903 # define PATFETCH_RAW(c) \
1904 do {if (p == pend) return REG_EEND; \
1905 c = (UCHAR_T) *p++; \
1908 /* Go backwards one character in the pattern. */
1909 # define PATUNFETCH p--
1912 /* If `translate' is non-null, return translate[D], else just D. We
1913 cast the subscript to translate because some data is declared as
1914 `char *', to avoid warnings when a string constant is passed. But
1915 when we use a character as a subscript we must make it unsigned. */
1916 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1917 because it is impossible to allocate 4GB array for some encodings
1918 which have 4 byte character_set like UCS4. */
1922 # define TRANSLATE(d) \
1923 ((translate && ((UCHAR_T) (d)) <= 0xff) \
1924 ? (char) translate[(unsigned char) (d)] : (d))
1926 # define TRANSLATE(d) \
1927 (translate ? (char) translate[(unsigned char) (d)] : (d))
1932 /* Macros for outputting the compiled pattern into `buffer'. */
1934 /* If the buffer isn't allocated when it comes in, use this. */
1935 # define INIT_BUF_SIZE (32 * sizeof(UCHAR_T))
1937 /* Make sure we have at least N more bytes of space in buffer. */
1939 # define GET_BUFFER_SPACE(n) \
1940 while (((unsigned long)b - (unsigned long)COMPILED_BUFFER_VAR \
1941 + (n)*sizeof(CHAR_T)) > bufp->allocated) \
1944 # define GET_BUFFER_SPACE(n) \
1945 while ((unsigned long) (b - bufp->buffer + (n)) > bufp->allocated) \
1949 /* Make sure we have one more byte of buffer space and then add C to it. */
1950 # define BUF_PUSH(c) \
1952 GET_BUFFER_SPACE (1); \
1953 *b++ = (UCHAR_T) (c); \
1957 /* Ensure we have two more bytes of buffer space and then append C1 and C2. */
1958 # define BUF_PUSH_2(c1, c2) \
1960 GET_BUFFER_SPACE (2); \
1961 *b++ = (UCHAR_T) (c1); \
1962 *b++ = (UCHAR_T) (c2); \
1966 /* As with BUF_PUSH_2, except for three bytes. */
1967 # define BUF_PUSH_3(c1, c2, c3) \
1969 GET_BUFFER_SPACE (3); \
1970 *b++ = (UCHAR_T) (c1); \
1971 *b++ = (UCHAR_T) (c2); \
1972 *b++ = (UCHAR_T) (c3); \
1975 /* Store a jump with opcode OP at LOC to location TO. We store a
1976 relative address offset by the three bytes the jump itself occupies. */
1977 # define STORE_JUMP(op, loc, to) \
1978 PREFIX(store_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)))
1980 /* Likewise, for a two-argument jump. */
1981 # define STORE_JUMP2(op, loc, to, arg) \
1982 PREFIX(store_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), arg)
1984 /* Like `STORE_JUMP', but for inserting. Assume `b' is the buffer end. */
1985 # define INSERT_JUMP(op, loc, to) \
1986 PREFIX(insert_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), b)
1988 /* Like `STORE_JUMP2', but for inserting. Assume `b' is the buffer end. */
1989 # define INSERT_JUMP2(op, loc, to, arg) \
1990 PREFIX(insert_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)),\
1993 /* This is not an arbitrary limit: the arguments which represent offsets
1994 into the pattern are two bytes long. So if 2^16 bytes turns out to
1995 be too small, many things would have to change. */
1996 /* Any other compiler which, like MSC, has allocation limit below 2^16
1997 bytes will have to use approach similar to what was done below for
1998 MSC and drop MAX_BUF_SIZE a bit. Otherwise you may end up
1999 reallocating to 0 bytes. Such thing is not going to work too well.
2000 You have been warned!! */
2001 # ifndef DEFINED_ONCE
2002 # if defined _MSC_VER && !defined WIN32
2003 /* Microsoft C 16-bit versions limit malloc to approx 65512 bytes.
2004 The REALLOC define eliminates a flurry of conversion warnings,
2005 but is not required. */
2006 # define MAX_BUF_SIZE 65500L
2007 # define REALLOC(p,s) realloc ((p), (size_t) (s))
2009 # define MAX_BUF_SIZE (1L << 16)
2010 # define REALLOC(p,s) realloc ((p), (s))
2013 /* Extend the buffer by twice its current size via realloc and
2014 reset the pointers that pointed into the old block to point to the
2015 correct places in the new one. If extending the buffer results in it
2016 being larger than MAX_BUF_SIZE, then flag memory exhausted. */
2017 # if __BOUNDED_POINTERS__
2018 # define SET_HIGH_BOUND(P) (__ptrhigh (P) = __ptrlow (P) + bufp->allocated)
2019 # define MOVE_BUFFER_POINTER(P) \
2020 (__ptrlow (P) += incr, SET_HIGH_BOUND (P), __ptrvalue (P) += incr)
2021 # define ELSE_EXTEND_BUFFER_HIGH_BOUND \
2024 SET_HIGH_BOUND (b); \
2025 SET_HIGH_BOUND (begalt); \
2026 if (fixup_alt_jump) \
2027 SET_HIGH_BOUND (fixup_alt_jump); \
2029 SET_HIGH_BOUND (laststart); \
2030 if (pending_exact) \
2031 SET_HIGH_BOUND (pending_exact); \
2034 # define MOVE_BUFFER_POINTER(P) (P) += incr
2035 # define ELSE_EXTEND_BUFFER_HIGH_BOUND
2037 # endif /* not DEFINED_ONCE */
2040 # define EXTEND_BUFFER() \
2042 UCHAR_T *old_buffer = COMPILED_BUFFER_VAR; \
2044 if (bufp->allocated + sizeof(UCHAR_T) > MAX_BUF_SIZE) \
2046 bufp->allocated <<= 1; \
2047 if (bufp->allocated > MAX_BUF_SIZE) \
2048 bufp->allocated = MAX_BUF_SIZE; \
2049 /* How many characters the new buffer can have? */ \
2050 wchar_count = bufp->allocated / sizeof(UCHAR_T); \
2051 if (wchar_count == 0) wchar_count = 1; \
2052 /* Truncate the buffer to CHAR_T align. */ \
2053 bufp->allocated = wchar_count * sizeof(UCHAR_T); \
2054 RETALLOC (COMPILED_BUFFER_VAR, wchar_count, UCHAR_T); \
2055 bufp->buffer = (char*)COMPILED_BUFFER_VAR; \
2056 if (COMPILED_BUFFER_VAR == NULL) \
2057 return REG_ESPACE; \
2058 /* If the buffer moved, move all the pointers into it. */ \
2059 if (old_buffer != COMPILED_BUFFER_VAR) \
2061 int incr = COMPILED_BUFFER_VAR - old_buffer; \
2062 MOVE_BUFFER_POINTER (b); \
2063 MOVE_BUFFER_POINTER (begalt); \
2064 if (fixup_alt_jump) \
2065 MOVE_BUFFER_POINTER (fixup_alt_jump); \
2067 MOVE_BUFFER_POINTER (laststart); \
2068 if (pending_exact) \
2069 MOVE_BUFFER_POINTER (pending_exact); \
2071 ELSE_EXTEND_BUFFER_HIGH_BOUND \
2074 # define EXTEND_BUFFER() \
2076 UCHAR_T *old_buffer = COMPILED_BUFFER_VAR; \
2077 if (bufp->allocated == MAX_BUF_SIZE) \
2079 bufp->allocated <<= 1; \
2080 if (bufp->allocated > MAX_BUF_SIZE) \
2081 bufp->allocated = MAX_BUF_SIZE; \
2083 = (UCHAR_T *) REALLOC (COMPILED_BUFFER_VAR, bufp->allocated); \
2084 if (COMPILED_BUFFER_VAR == NULL) \
2085 return REG_ESPACE; \
2086 /* If the buffer moved, move all the pointers into it. */ \
2087 if (old_buffer != COMPILED_BUFFER_VAR) \
2089 int incr = COMPILED_BUFFER_VAR - old_buffer; \
2090 MOVE_BUFFER_POINTER (b); \
2091 MOVE_BUFFER_POINTER (begalt); \
2092 if (fixup_alt_jump) \
2093 MOVE_BUFFER_POINTER (fixup_alt_jump); \
2095 MOVE_BUFFER_POINTER (laststart); \
2096 if (pending_exact) \
2097 MOVE_BUFFER_POINTER (pending_exact); \
2099 ELSE_EXTEND_BUFFER_HIGH_BOUND \
2103 # ifndef DEFINED_ONCE
2104 /* Since we have one byte reserved for the register number argument to
2105 {start,stop}_memory, the maximum number of groups we can report
2106 things about is what fits in that byte. */
2107 # define MAX_REGNUM 255
2109 /* But patterns can have more than `MAX_REGNUM' registers. We just
2110 ignore the excess. */
2111 typedef unsigned regnum_t;
2114 /* Macros for the compile stack. */
2116 /* Since offsets can go either forwards or backwards, this type needs to
2117 be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1. */
2118 /* int may be not enough when sizeof(int) == 2. */
2119 typedef long pattern_offset_t;
2123 pattern_offset_t begalt_offset;
2124 pattern_offset_t fixup_alt_jump;
2125 pattern_offset_t inner_group_offset;
2126 pattern_offset_t laststart_offset;
2128 } compile_stack_elt_t;
2133 compile_stack_elt_t *stack;
2135 unsigned avail; /* Offset of next open position. */
2136 } compile_stack_type;
2139 # define INIT_COMPILE_STACK_SIZE 32
2141 # define COMPILE_STACK_EMPTY (compile_stack.avail == 0)
2142 # define COMPILE_STACK_FULL (compile_stack.avail == compile_stack.size)
2144 /* The next available element. */
2145 # define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
2147 # endif /* not DEFINED_ONCE */
2149 /* Set the bit for character C in a list. */
2150 # ifndef DEFINED_ONCE
2151 # define SET_LIST_BIT(c) \
2152 (b[((unsigned char) (c)) / BYTEWIDTH] \
2153 |= 1 << (((unsigned char) c) % BYTEWIDTH))
2154 # endif /* DEFINED_ONCE */
2156 /* Get the next unsigned number in the uncompiled pattern. */
2157 # define GET_UNSIGNED_NUMBER(num) \
2162 if (c < '0' || c > '9') \
2164 if (num <= RE_DUP_MAX) \
2168 num = num * 10 + c - '0'; \
2173 # ifndef DEFINED_ONCE
2174 # if defined _LIBC || WIDE_CHAR_SUPPORT
2175 /* The GNU C library provides support for user-defined character classes
2176 and the functions from ISO C amendement 1. */
2177 # ifdef CHARCLASS_NAME_MAX
2178 # define CHAR_CLASS_MAX_LENGTH CHARCLASS_NAME_MAX
2180 /* This shouldn't happen but some implementation might still have this
2181 problem. Use a reasonable default value. */
2182 # define CHAR_CLASS_MAX_LENGTH 256
2186 # define IS_CHAR_CLASS(string) __wctype (string)
2188 # define IS_CHAR_CLASS(string) wctype (string)
2191 # define CHAR_CLASS_MAX_LENGTH 6 /* Namely, `xdigit'. */
2193 # define IS_CHAR_CLASS(string) \
2194 (STREQ (string, "alpha") || STREQ (string, "upper") \
2195 || STREQ (string, "lower") || STREQ (string, "digit") \
2196 || STREQ (string, "alnum") || STREQ (string, "xdigit") \
2197 || STREQ (string, "space") || STREQ (string, "print") \
2198 || STREQ (string, "punct") || STREQ (string, "graph") \
2199 || STREQ (string, "cntrl") || STREQ (string, "blank"))
2201 # endif /* DEFINED_ONCE */
2203 # ifndef MATCH_MAY_ALLOCATE
2205 /* If we cannot allocate large objects within re_match_2_internal,
2206 we make the fail stack and register vectors global.
2207 The fail stack, we grow to the maximum size when a regexp
2209 The register vectors, we adjust in size each time we
2210 compile a regexp, according to the number of registers it needs. */
2212 static PREFIX(fail_stack_type) fail_stack;
2214 /* Size with which the following vectors are currently allocated.
2215 That is so we can make them bigger as needed,
2216 but never make them smaller. */
2217 # ifdef DEFINED_ONCE
2218 static int regs_allocated_size;
2220 static const char ** regstart, ** regend;
2221 static const char ** old_regstart, ** old_regend;
2222 static const char **best_regstart, **best_regend;
2223 static const char **reg_dummy;
2224 # endif /* DEFINED_ONCE */
2226 static PREFIX(register_info_type) *PREFIX(reg_info);
2227 static PREFIX(register_info_type) *PREFIX(reg_info_dummy);
2229 /* Make the register vectors big enough for NUM_REGS registers,
2230 but don't make them smaller. */
2233 PREFIX(regex_grow_registers) (int num_regs)
2235 if (num_regs > regs_allocated_size)
2237 RETALLOC_IF (regstart, num_regs, const char *);
2238 RETALLOC_IF (regend, num_regs, const char *);
2239 RETALLOC_IF (old_regstart, num_regs, const char *);
2240 RETALLOC_IF (old_regend, num_regs, const char *);
2241 RETALLOC_IF (best_regstart, num_regs, const char *);
2242 RETALLOC_IF (best_regend, num_regs, const char *);
2243 RETALLOC_IF (PREFIX(reg_info), num_regs, PREFIX(register_info_type));
2244 RETALLOC_IF (reg_dummy, num_regs, const char *);
2245 RETALLOC_IF (PREFIX(reg_info_dummy), num_regs, PREFIX(register_info_type));
2247 regs_allocated_size = num_regs;
2251 # endif /* not MATCH_MAY_ALLOCATE */
2253 # ifndef DEFINED_ONCE
2254 static boolean group_in_compile_stack (compile_stack_type
2257 # endif /* not DEFINED_ONCE */
2259 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
2260 Returns one of error codes defined in `regex.h', or zero for success.
2262 Assumes the `allocated' (and perhaps `buffer') and `translate'
2263 fields are set in BUFP on entry.
2265 If it succeeds, results are put in BUFP (if it returns an error, the
2266 contents of BUFP are undefined):
2267 `buffer' is the compiled pattern;
2268 `syntax' is set to SYNTAX;
2269 `used' is set to the length of the compiled pattern;
2270 `fastmap_accurate' is zero;
2271 `re_nsub' is the number of subexpressions in PATTERN;
2272 `not_bol' and `not_eol' are zero;
2274 The `fastmap' and `newline_anchor' fields are neither
2275 examined nor set. */
2277 /* Return, freeing storage we allocated. */
2279 # define FREE_STACK_RETURN(value) \
2280 return (free(pattern), free(mbs_offset), free(is_binary), free (compile_stack.stack), value)
2282 # define FREE_STACK_RETURN(value) \
2283 return (free (compile_stack.stack), value)
2286 static reg_errcode_t
2287 PREFIX(regex_compile) (const char *ARG_PREFIX(pattern),
2288 size_t ARG_PREFIX(size),
2289 reg_syntax_t syntax,
2290 struct re_pattern_buffer *bufp)
2292 /* We fetch characters from PATTERN here. Even though PATTERN is
2293 `char *' (i.e., signed), we declare these variables as unsigned, so
2294 they can be reliably used as array indices. */
2295 register UCHAR_T c, c1;
2298 /* A temporary space to keep wchar_t pattern and compiled pattern. */
2299 CHAR_T *pattern, *COMPILED_BUFFER_VAR;
2301 /* offset buffer for optimization. See convert_mbs_to_wc. */
2302 int *mbs_offset = NULL;
2303 /* It hold whether each wchar_t is binary data or not. */
2304 char *is_binary = NULL;
2305 /* A flag whether exactn is handling binary data or not. */
2306 char is_exactn_bin = FALSE;
2309 /* A random temporary spot in PATTERN. */
2312 /* Points to the end of the buffer, where we should append. */
2313 register UCHAR_T *b;
2315 /* Keeps track of unclosed groups. */
2316 compile_stack_type compile_stack;
2318 /* Points to the current (ending) position in the pattern. */
2323 const CHAR_T *p = pattern;
2324 const CHAR_T *pend = pattern + size;
2327 /* How to translate the characters in the pattern. */
2328 RE_TRANSLATE_TYPE translate = bufp->translate;
2330 /* Address of the count-byte of the most recently inserted `exactn'
2331 command. This makes it possible to tell if a new exact-match
2332 character can be added to that command or if the character requires
2333 a new `exactn' command. */
2334 UCHAR_T *pending_exact = 0;
2336 /* Address of start of the most recently finished expression.
2337 This tells, e.g., postfix * where to find the start of its
2338 operand. Reset at the beginning of groups and alternatives. */
2339 UCHAR_T *laststart = 0;
2341 /* Address of beginning of regexp, or inside of last group. */
2344 /* Address of the place where a forward jump should go to the end of
2345 the containing expression. Each alternative of an `or' -- except the
2346 last -- ends with a forward jump of this sort. */
2347 UCHAR_T *fixup_alt_jump = 0;
2349 /* Counts open-groups as they are encountered. Remembered for the
2350 matching close-group on the compile stack, so the same register
2351 number is put in the stop_memory as the start_memory. */
2352 regnum_t regnum = 0;
2355 /* Initialize the wchar_t PATTERN and offset_buffer. */
2356 p = pend = pattern = TALLOC(csize + 1, CHAR_T);
2357 mbs_offset = TALLOC(csize + 1, int);
2358 is_binary = TALLOC(csize + 1, char);
2359 if (pattern == NULL || mbs_offset == NULL || is_binary == NULL)
2366 pattern[csize] = L'\0'; /* sentinel */
2367 size = convert_mbs_to_wcs(pattern, cpattern, csize, mbs_offset, is_binary);
2379 DEBUG_PRINT1 ("\nCompiling pattern: ");
2382 unsigned debug_count;
2384 for (debug_count = 0; debug_count < size; debug_count++)
2385 PUT_CHAR (pattern[debug_count]);
2390 /* Initialize the compile stack. */
2391 compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
2392 if (compile_stack.stack == NULL)
2402 compile_stack.size = INIT_COMPILE_STACK_SIZE;
2403 compile_stack.avail = 0;
2405 /* Initialize the pattern buffer. */
2406 bufp->syntax = syntax;
2407 bufp->fastmap_accurate = 0;
2408 bufp->not_bol = bufp->not_eol = 0;
2410 /* Set `used' to zero, so that if we return an error, the pattern
2411 printer (for debugging) will think there's no pattern. We reset it
2415 /* Always count groups, whether or not bufp->no_sub is set. */
2418 #if !defined emacs && !defined SYNTAX_TABLE
2419 /* Initialize the syntax table. */
2420 init_syntax_once ();
2423 if (bufp->allocated == 0)
2426 { /* If zero allocated, but buffer is non-null, try to realloc
2427 enough space. This loses if buffer's address is bogus, but
2428 that is the user's responsibility. */
2430 /* Free bufp->buffer and allocate an array for wchar_t pattern
2433 COMPILED_BUFFER_VAR = TALLOC (INIT_BUF_SIZE/sizeof(UCHAR_T),
2436 RETALLOC (COMPILED_BUFFER_VAR, INIT_BUF_SIZE, UCHAR_T);
2440 { /* Caller did not allocate a buffer. Do it for them. */
2441 COMPILED_BUFFER_VAR = TALLOC (INIT_BUF_SIZE / sizeof(UCHAR_T),
2445 if (!COMPILED_BUFFER_VAR) FREE_STACK_RETURN (REG_ESPACE);
2447 bufp->buffer = (char*)COMPILED_BUFFER_VAR;
2449 bufp->allocated = INIT_BUF_SIZE;
2453 COMPILED_BUFFER_VAR = (UCHAR_T*) bufp->buffer;
2456 begalt = b = COMPILED_BUFFER_VAR;
2458 /* Loop through the uncompiled pattern until we're at the end. */
2467 if ( /* If at start of pattern, it's an operator. */
2469 /* If context independent, it's an operator. */
2470 || syntax & RE_CONTEXT_INDEP_ANCHORS
2471 /* Otherwise, depends on what's come before. */
2472 || PREFIX(at_begline_loc_p) (pattern, p, syntax))
2482 if ( /* If at end of pattern, it's an operator. */
2484 /* If context independent, it's an operator. */
2485 || syntax & RE_CONTEXT_INDEP_ANCHORS
2486 /* Otherwise, depends on what's next. */
2487 || PREFIX(at_endline_loc_p) (p, pend, syntax))
2497 if ((syntax & RE_BK_PLUS_QM)
2498 || (syntax & RE_LIMITED_OPS))
2502 /* If there is no previous pattern... */
2505 if (syntax & RE_CONTEXT_INVALID_OPS)
2506 FREE_STACK_RETURN (REG_BADRPT);
2507 else if (!(syntax & RE_CONTEXT_INDEP_OPS))
2512 /* Are we optimizing this jump? */
2513 boolean keep_string_p = false;
2515 /* 1 means zero (many) matches is allowed. */
2516 char zero_times_ok = 0, many_times_ok = 0;
2518 /* If there is a sequence of repetition chars, collapse it
2519 down to just one (the right one). We can't combine
2520 interval operators with these because of, e.g., `a{2}*',
2521 which should only match an even number of `a's. */
2525 zero_times_ok |= c != '+';
2526 many_times_ok |= c != '?';
2534 || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
2537 else if (syntax & RE_BK_PLUS_QM && c == '\\')
2539 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2542 if (!(c1 == '+' || c1 == '?'))
2557 /* If we get here, we found another repeat character. */
2560 /* Star, etc. applied to an empty pattern is equivalent
2561 to an empty pattern. */
2565 /* Now we know whether or not zero matches is allowed
2566 and also whether or not two or more matches is allowed. */
2568 { /* More than one repetition is allowed, so put in at the
2569 end a backward relative jump from `b' to before the next
2570 jump we're going to put in below (which jumps from
2571 laststart to after this jump).
2573 But if we are at the `*' in the exact sequence `.*\n',
2574 insert an unconditional jump backwards to the .,
2575 instead of the beginning of the loop. This way we only
2576 push a failure point once, instead of every time
2577 through the loop. */
2578 assert (p - 1 > pattern);
2580 /* Allocate the space for the jump. */
2581 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2583 /* We know we are not at the first character of the pattern,
2584 because laststart was nonzero. And we've already
2585 incremented `p', by the way, to be the character after
2586 the `*'. Do we have to do something analogous here
2587 for null bytes, because of RE_DOT_NOT_NULL? */
2588 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
2590 && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
2591 && !(syntax & RE_DOT_NEWLINE))
2592 { /* We have .*\n. */
2593 STORE_JUMP (jump, b, laststart);
2594 keep_string_p = true;
2597 /* Anything else. */
2598 STORE_JUMP (maybe_pop_jump, b, laststart -
2599 (1 + OFFSET_ADDRESS_SIZE));
2601 /* We've added more stuff to the buffer. */
2602 b += 1 + OFFSET_ADDRESS_SIZE;
2605 /* On failure, jump from laststart to b + 3, which will be the
2606 end of the buffer after this jump is inserted. */
2607 /* ifdef WCHAR, 'b + 1 + OFFSET_ADDRESS_SIZE' instead of
2609 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2610 INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
2612 laststart, b + 1 + OFFSET_ADDRESS_SIZE);
2614 b += 1 + OFFSET_ADDRESS_SIZE;
2618 /* At least one repetition is required, so insert a
2619 `dummy_failure_jump' before the initial
2620 `on_failure_jump' instruction of the loop. This
2621 effects a skip over that instruction the first time
2622 we hit that loop. */
2623 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2624 INSERT_JUMP (dummy_failure_jump, laststart, laststart +
2625 2 + 2 * OFFSET_ADDRESS_SIZE);
2626 b += 1 + OFFSET_ADDRESS_SIZE;
2640 boolean had_char_class = false;
2642 CHAR_T range_start = 0xffffffff;
2644 unsigned int range_start = 0xffffffff;
2646 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2649 /* We assume a charset(_not) structure as a wchar_t array.
2650 charset[0] = (re_opcode_t) charset(_not)
2651 charset[1] = l (= length of char_classes)
2652 charset[2] = m (= length of collating_symbols)
2653 charset[3] = n (= length of equivalence_classes)
2654 charset[4] = o (= length of char_ranges)
2655 charset[5] = p (= length of chars)
2657 charset[6] = char_class (wctype_t)
2658 charset[6+CHAR_CLASS_SIZE] = char_class (wctype_t)
2660 charset[l+5] = char_class (wctype_t)
2662 charset[l+6] = collating_symbol (wchar_t)
2664 charset[l+m+5] = collating_symbol (wchar_t)
2665 ifdef _LIBC we use the index if
2666 _NL_COLLATE_SYMB_EXTRAMB instead of
2669 charset[l+m+6] = equivalence_classes (wchar_t)
2671 charset[l+m+n+5] = equivalence_classes (wchar_t)
2672 ifdef _LIBC we use the index in
2673 _NL_COLLATE_WEIGHT instead of
2676 charset[l+m+n+6] = range_start
2677 charset[l+m+n+7] = range_end
2679 charset[l+m+n+2o+4] = range_start
2680 charset[l+m+n+2o+5] = range_end
2681 ifdef _LIBC we use the value looked up
2682 in _NL_COLLATE_COLLSEQ instead of
2685 charset[l+m+n+2o+6] = char
2687 charset[l+m+n+2o+p+5] = char
2691 /* We need at least 6 spaces: the opcode, the length of
2692 char_classes, the length of collating_symbols, the length of
2693 equivalence_classes, the length of char_ranges, the length of
2695 GET_BUFFER_SPACE (6);
2697 /* Save b as laststart. And We use laststart as the pointer
2698 to the first element of the charset here.
2699 In other words, laststart[i] indicates charset[i]. */
2702 /* We test `*p == '^' twice, instead of using an if
2703 statement, so we only need one BUF_PUSH. */
2704 BUF_PUSH (*p == '^' ? charset_not : charset);
2708 /* Push the length of char_classes, the length of
2709 collating_symbols, the length of equivalence_classes, the
2710 length of char_ranges and the length of chars. */
2711 BUF_PUSH_3 (0, 0, 0);
2714 /* Remember the first position in the bracket expression. */
2717 /* charset_not matches newline according to a syntax bit. */
2718 if ((re_opcode_t) b[-6] == charset_not
2719 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
2722 laststart[5]++; /* Update the length of characters */
2725 /* Read in characters and ranges, setting map bits. */
2728 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2732 /* \ might escape characters inside [...] and [^...]. */
2733 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
2735 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2739 laststart[5]++; /* Update the length of chars */
2744 /* Could be the end of the bracket expression. If it's
2745 not (i.e., when the bracket expression is `[]' so
2746 far), the ']' character bit gets set way below. */
2747 if (c == ']' && p != p1 + 1)
2750 /* Look ahead to see if it's a range when the last thing
2751 was a character class. */
2752 if (had_char_class && c == '-' && *p != ']')
2753 FREE_STACK_RETURN (REG_ERANGE);
2755 /* Look ahead to see if it's a range when the last thing
2756 was a character: if this is a hyphen not at the
2757 beginning or the end of a list, then it's the range
2760 && !(p - 2 >= pattern && p[-2] == '[')
2761 && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
2765 /* Allocate the space for range_start and range_end. */
2766 GET_BUFFER_SPACE (2);
2767 /* Update the pointer to indicate end of buffer. */
2769 ret = wcs_compile_range (range_start, &p, pend, translate,
2770 syntax, b, laststart);
2771 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2772 range_start = 0xffffffff;
2774 else if (p[0] == '-' && p[1] != ']')
2775 { /* This handles ranges made up of characters only. */
2778 /* Move past the `-'. */
2780 /* Allocate the space for range_start and range_end. */
2781 GET_BUFFER_SPACE (2);
2782 /* Update the pointer to indicate end of buffer. */
2784 ret = wcs_compile_range (c, &p, pend, translate, syntax, b,
2786 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2787 range_start = 0xffffffff;
2790 /* See if we're at the beginning of a possible character
2792 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
2793 { /* Leave room for the null. */
2794 char str[CHAR_CLASS_MAX_LENGTH + 1];
2799 /* If pattern is `[[:'. */
2800 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2805 if ((c == ':' && *p == ']') || p == pend)
2807 if (c1 < CHAR_CLASS_MAX_LENGTH)
2810 /* This is in any case an invalid class name. */
2815 /* If isn't a word bracketed by `[:' and `:]':
2816 undo the ending character, the letters, and leave
2817 the leading `:' and `[' (but store them as character). */
2818 if (c == ':' && *p == ']')
2823 /* Query the character class as wctype_t. */
2824 wt = IS_CHAR_CLASS (str);
2826 FREE_STACK_RETURN (REG_ECTYPE);
2828 /* Throw away the ] at the end of the character
2832 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2834 /* Allocate the space for character class. */
2835 GET_BUFFER_SPACE(CHAR_CLASS_SIZE);
2836 /* Update the pointer to indicate end of buffer. */
2837 b += CHAR_CLASS_SIZE;
2838 /* Move data which follow character classes
2839 not to violate the data. */
2840 insert_space(CHAR_CLASS_SIZE,
2841 laststart + 6 + laststart[1],
2843 alignedp = ((uintptr_t)(laststart + 6 + laststart[1])
2844 + __alignof__(wctype_t) - 1)
2845 & ~(uintptr_t)(__alignof__(wctype_t) - 1);
2846 /* Store the character class. */
2847 *((wctype_t*)alignedp) = wt;
2848 /* Update length of char_classes */
2849 laststart[1] += CHAR_CLASS_SIZE;
2851 had_char_class = true;
2860 laststart[5] += 2; /* Update the length of characters */
2862 had_char_class = false;
2865 else if (syntax & RE_CHAR_CLASSES && c == '[' && (*p == '='
2868 CHAR_T str[128]; /* Should be large enough. */
2869 CHAR_T delim = *p; /* '=' or '.' */
2872 _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
2877 /* If pattern is `[[=' or '[[.'. */
2878 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2883 if ((c == delim && *p == ']') || p == pend)
2885 if (c1 < sizeof (str) - 1)
2888 /* This is in any case an invalid class name. */
2893 if (c == delim && *p == ']' && str[0] != '\0')
2895 unsigned int i, offset;
2896 /* If we have no collation data we use the default
2897 collation in which each character is in a class
2898 by itself. It also means that ASCII is the
2899 character set and therefore we cannot have character
2900 with more than one byte in the multibyte
2903 /* If not defined _LIBC, we push the name and
2904 `\0' for the sake of matching performance. */
2905 int datasize = c1 + 1;
2913 FREE_STACK_RETURN (REG_ECOLLATE);
2918 const int32_t *table;
2919 const int32_t *weights;
2920 const int32_t *extra;
2921 const int32_t *indirect;
2924 /* This #include defines a local function! */
2925 # include <locale/weightwc.h>
2929 /* We push the index for equivalence class. */
2932 table = (const int32_t *)
2933 _NL_CURRENT (LC_COLLATE,
2934 _NL_COLLATE_TABLEWC);
2935 weights = (const int32_t *)
2936 _NL_CURRENT (LC_COLLATE,
2937 _NL_COLLATE_WEIGHTWC);
2938 extra = (const int32_t *)
2939 _NL_CURRENT (LC_COLLATE,
2940 _NL_COLLATE_EXTRAWC);
2941 indirect = (const int32_t *)
2942 _NL_CURRENT (LC_COLLATE,
2943 _NL_COLLATE_INDIRECTWC);
2945 idx = findidx ((const wint_t**)&cp);
2946 if (idx == 0 || cp < (wint_t*) str + c1)
2947 /* This is no valid character. */
2948 FREE_STACK_RETURN (REG_ECOLLATE);
2950 str[0] = (wchar_t)idx;
2952 else /* delim == '.' */
2954 /* We push collation sequence value
2955 for collating symbol. */
2957 const int32_t *symb_table;
2958 const unsigned char *extra;
2965 /* We have to convert the name to a single-byte
2966 string. This is possible since the names
2967 consist of ASCII characters and the internal
2968 representation is UCS4. */
2969 for (i = 0; i < c1; ++i)
2970 char_str[i] = str[i];
2973 _NL_CURRENT_WORD (LC_COLLATE,
2974 _NL_COLLATE_SYMB_HASH_SIZEMB);
2975 symb_table = (const int32_t *)
2976 _NL_CURRENT (LC_COLLATE,
2977 _NL_COLLATE_SYMB_TABLEMB);
2978 extra = (const unsigned char *)
2979 _NL_CURRENT (LC_COLLATE,
2980 _NL_COLLATE_SYMB_EXTRAMB);
2982 /* Locate the character in the hashing table. */
2983 hash = elem_hash (char_str, c1);
2986 elem = hash % table_size;
2987 second = hash % (table_size - 2);
2988 while (symb_table[2 * elem] != 0)
2990 /* First compare the hashing value. */
2991 if (symb_table[2 * elem] == hash
2992 && c1 == extra[symb_table[2 * elem + 1]]
2993 && memcmp (char_str,
2994 &extra[symb_table[2 * elem + 1]
2997 /* Yep, this is the entry. */
2998 idx = symb_table[2 * elem + 1];
2999 idx += 1 + extra[idx];
3007 if (symb_table[2 * elem] != 0)
3009 /* Compute the index of the byte sequence
3011 idx += 1 + extra[idx];
3012 /* Adjust for the alignment. */
3013 idx = (idx + 3) & ~3;
3015 str[0] = (wchar_t) idx + 4;
3017 else if (symb_table[2 * elem] == 0 && c1 == 1)
3019 /* No valid character. Match it as a
3020 single byte character. */
3021 had_char_class = false;
3023 /* Update the length of characters */
3025 range_start = str[0];
3027 /* Throw away the ] at the end of the
3028 collating symbol. */
3030 /* exit from the switch block. */
3034 FREE_STACK_RETURN (REG_ECOLLATE);
3039 /* Throw away the ] at the end of the equivalence
3040 class (or collating symbol). */
3043 /* Allocate the space for the equivalence class
3044 (or collating symbol) (and '\0' if needed). */
3045 GET_BUFFER_SPACE(datasize);
3046 /* Update the pointer to indicate end of buffer. */
3050 { /* equivalence class */
3051 /* Calculate the offset of char_ranges,
3052 which is next to equivalence_classes. */
3053 offset = laststart[1] + laststart[2]
3056 insert_space(datasize, laststart + offset, b - 1);
3058 /* Write the equivalence_class and \0. */
3059 for (i = 0 ; i < datasize ; i++)
3060 laststart[offset + i] = str[i];
3062 /* Update the length of equivalence_classes. */
3063 laststart[3] += datasize;
3064 had_char_class = true;
3066 else /* delim == '.' */
3067 { /* collating symbol */
3068 /* Calculate the offset of the equivalence_classes,
3069 which is next to collating_symbols. */
3070 offset = laststart[1] + laststart[2] + 6;
3071 /* Insert space and write the collationg_symbol
3073 insert_space(datasize, laststart + offset, b-1);
3074 for (i = 0 ; i < datasize ; i++)
3075 laststart[offset + i] = str[i];
3077 /* In re_match_2_internal if range_start < -1, we
3078 assume -range_start is the offset of the
3079 collating symbol which is specified as
3080 the character of the range start. So we assign
3081 -(laststart[1] + laststart[2] + 6) to
3083 range_start = -(laststart[1] + laststart[2] + 6);
3084 /* Update the length of collating_symbol. */
3085 laststart[2] += datasize;
3086 had_char_class = false;
3096 laststart[5] += 2; /* Update the length of characters */
3097 range_start = delim;
3098 had_char_class = false;
3103 had_char_class = false;
3105 laststart[5]++; /* Update the length of characters */
3111 /* Ensure that we have enough space to push a charset: the
3112 opcode, the length count, and the bitset; 34 bytes in all. */
3113 GET_BUFFER_SPACE (34);
3117 /* We test `*p == '^' twice, instead of using an if
3118 statement, so we only need one BUF_PUSH. */
3119 BUF_PUSH (*p == '^' ? charset_not : charset);
3123 /* Remember the first position in the bracket expression. */
3126 /* Push the number of bytes in the bitmap. */
3127 BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
3129 /* Clear the whole map. */
3130 bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
3132 /* charset_not matches newline according to a syntax bit. */
3133 if ((re_opcode_t) b[-2] == charset_not
3134 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
3135 SET_LIST_BIT ('\n');
3137 /* Read in characters and ranges, setting map bits. */
3140 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3144 /* \ might escape characters inside [...] and [^...]. */
3145 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
3147 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
3155 /* Could be the end of the bracket expression. If it's
3156 not (i.e., when the bracket expression is `[]' so
3157 far), the ']' character bit gets set way below. */
3158 if (c == ']' && p != p1 + 1)
3161 /* Look ahead to see if it's a range when the last thing
3162 was a character class. */
3163 if (had_char_class && c == '-' && *p != ']')
3164 FREE_STACK_RETURN (REG_ERANGE);
3166 /* Look ahead to see if it's a range when the last thing
3167 was a character: if this is a hyphen not at the
3168 beginning or the end of a list, then it's the range
3171 && !(p - 2 >= pattern && p[-2] == '[')
3172 && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
3176 = byte_compile_range (range_start, &p, pend, translate,
3178 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
3179 range_start = 0xffffffff;
3182 else if (p[0] == '-' && p[1] != ']')
3183 { /* This handles ranges made up of characters only. */
3186 /* Move past the `-'. */
3189 ret = byte_compile_range (c, &p, pend, translate, syntax, b);
3190 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
3191 range_start = 0xffffffff;
3194 /* See if we're at the beginning of a possible character
3197 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
3198 { /* Leave room for the null. */
3199 char str[CHAR_CLASS_MAX_LENGTH + 1];
3204 /* If pattern is `[[:'. */
3205 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3210 if ((c == ':' && *p == ']') || p == pend)
3212 if (c1 < CHAR_CLASS_MAX_LENGTH)
3215 /* This is in any case an invalid class name. */
3220 /* If isn't a word bracketed by `[:' and `:]':
3221 undo the ending character, the letters, and leave
3222 the leading `:' and `[' (but set bits for them). */
3223 if (c == ':' && *p == ']')
3225 # if defined _LIBC || WIDE_CHAR_SUPPORT
3226 boolean is_lower = STREQ (str, "lower");
3227 boolean is_upper = STREQ (str, "upper");
3231 wt = IS_CHAR_CLASS (str);
3233 FREE_STACK_RETURN (REG_ECTYPE);
3235 /* Throw away the ] at the end of the character
3239 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3241 for (ch = 0; ch < 1 << BYTEWIDTH; ++ch)
3243 if (iswctype (btowc (ch), wt))
3246 if (translate && (is_upper || is_lower)
3247 && (ISUPPER (ch) || ISLOWER (ch)))
3251 had_char_class = true;
3254 boolean is_alnum = STREQ (str, "alnum");
3255 boolean is_alpha = STREQ (str, "alpha");
3256 boolean is_blank = STREQ (str, "blank");
3257 boolean is_cntrl = STREQ (str, "cntrl");
3258 boolean is_digit = STREQ (str, "digit");
3259 boolean is_graph = STREQ (str, "graph");
3260 boolean is_lower = STREQ (str, "lower");
3261 boolean is_print = STREQ (str, "print");
3262 boolean is_punct = STREQ (str, "punct");
3263 boolean is_space = STREQ (str, "space");
3264 boolean is_upper = STREQ (str, "upper");
3265 boolean is_xdigit = STREQ (str, "xdigit");
3267 if (!IS_CHAR_CLASS (str))
3268 FREE_STACK_RETURN (REG_ECTYPE);
3270 /* Throw away the ] at the end of the character
3274 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3276 for (ch = 0; ch < 1 << BYTEWIDTH; ch++)
3278 /* This was split into 3 if's to
3279 avoid an arbitrary limit in some compiler. */
3280 if ( (is_alnum && ISALNUM (ch))
3281 || (is_alpha && ISALPHA (ch))
3282 || (is_blank && ISBLANK (ch))
3283 || (is_cntrl && ISCNTRL (ch)))
3285 if ( (is_digit && ISDIGIT (ch))
3286 || (is_graph && ISGRAPH (ch))
3287 || (is_lower && ISLOWER (ch))
3288 || (is_print && ISPRINT (ch)))
3290 if ( (is_punct && ISPUNCT (ch))
3291 || (is_space && ISSPACE (ch))
3292 || (is_upper && ISUPPER (ch))
3293 || (is_xdigit && ISXDIGIT (ch)))
3295 if ( translate && (is_upper || is_lower)
3296 && (ISUPPER (ch) || ISLOWER (ch)))
3299 had_char_class = true;
3300 # endif /* libc || wctype.h */
3310 had_char_class = false;
3313 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == '=')
3315 unsigned char str[MB_LEN_MAX + 1];
3318 _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3324 /* If pattern is `[[='. */
3325 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3330 if ((c == '=' && *p == ']') || p == pend)
3332 if (c1 < MB_LEN_MAX)
3335 /* This is in any case an invalid class name. */
3340 if (c == '=' && *p == ']' && str[0] != '\0')
3342 /* If we have no collation data we use the default
3343 collation in which each character is in a class
3344 by itself. It also means that ASCII is the
3345 character set and therefore we cannot have character
3346 with more than one byte in the multibyte
3353 FREE_STACK_RETURN (REG_ECOLLATE);
3355 /* Throw away the ] at the end of the equivalence
3359 /* Set the bit for the character. */
3360 SET_LIST_BIT (str[0]);
3365 /* Try to match the byte sequence in `str' against
3366 those known to the collate implementation.
3367 First find out whether the bytes in `str' are
3368 actually from exactly one character. */
3369 const int32_t *table;
3370 const unsigned char *weights;
3371 const unsigned char *extra;
3372 const int32_t *indirect;
3374 const unsigned char *cp = str;
3377 /* This #include defines a local function! */
3378 # include <locale/weight.h>
3380 table = (const int32_t *)
3381 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3382 weights = (const unsigned char *)
3383 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3384 extra = (const unsigned char *)
3385 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3386 indirect = (const int32_t *)
3387 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3389 idx = findidx (&cp);
3390 if (idx == 0 || cp < str + c1)
3391 /* This is no valid character. */
3392 FREE_STACK_RETURN (REG_ECOLLATE);
3394 /* Throw away the ] at the end of the equivalence
3398 /* Now we have to go throught the whole table
3399 and find all characters which have the same
3402 XXX Note that this is not entirely correct.
3403 we would have to match multibyte sequences
3404 but this is not possible with the current
3406 for (ch = 1; ch < 256; ++ch)
3407 /* XXX This test would have to be changed if we
3408 would allow matching multibyte sequences. */
3411 int32_t idx2 = table[ch];
3412 size_t len = weights[idx2];
3414 /* Test whether the lenghts match. */
3415 if (weights[idx] == len)
3417 /* They do. New compare the bytes of
3422 && (weights[idx + 1 + cnt]
3423 == weights[idx2 + 1 + cnt]))
3427 /* They match. Mark the character as
3434 had_char_class = true;
3444 had_char_class = false;
3447 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == '.')
3449 unsigned char str[128]; /* Should be large enough. */
3452 _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3458 /* If pattern is `[[.'. */
3459 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3464 if ((c == '.' && *p == ']') || p == pend)
3466 if (c1 < sizeof (str))
3469 /* This is in any case an invalid class name. */
3474 if (c == '.' && *p == ']' && str[0] != '\0')
3476 /* If we have no collation data we use the default
3477 collation in which each character is the name
3478 for its own class which contains only the one
3479 character. It also means that ASCII is the
3480 character set and therefore we cannot have character
3481 with more than one byte in the multibyte
3488 FREE_STACK_RETURN (REG_ECOLLATE);
3490 /* Throw away the ] at the end of the equivalence
3494 /* Set the bit for the character. */
3495 SET_LIST_BIT (str[0]);
3496 range_start = ((const unsigned char *) str)[0];
3501 /* Try to match the byte sequence in `str' against
3502 those known to the collate implementation.
3503 First find out whether the bytes in `str' are
3504 actually from exactly one character. */
3506 const int32_t *symb_table;
3507 const unsigned char *extra;
3514 _NL_CURRENT_WORD (LC_COLLATE,
3515 _NL_COLLATE_SYMB_HASH_SIZEMB);
3516 symb_table = (const int32_t *)
3517 _NL_CURRENT (LC_COLLATE,
3518 _NL_COLLATE_SYMB_TABLEMB);
3519 extra = (const unsigned char *)
3520 _NL_CURRENT (LC_COLLATE,
3521 _NL_COLLATE_SYMB_EXTRAMB);
3523 /* Locate the character in the hashing table. */
3524 hash = elem_hash (str, c1);
3527 elem = hash % table_size;
3528 second = hash % (table_size - 2);
3529 while (symb_table[2 * elem] != 0)
3531 /* First compare the hashing value. */
3532 if (symb_table[2 * elem] == hash
3533 && c1 == extra[symb_table[2 * elem + 1]]
3535 &extra[symb_table[2 * elem + 1]
3539 /* Yep, this is the entry. */
3540 idx = symb_table[2 * elem + 1];
3541 idx += 1 + extra[idx];
3549 if (symb_table[2 * elem] == 0)
3550 /* This is no valid character. */
3551 FREE_STACK_RETURN (REG_ECOLLATE);
3553 /* Throw away the ] at the end of the equivalence
3557 /* Now add the multibyte character(s) we found
3560 XXX Note that this is not entirely correct.
3561 we would have to match multibyte sequences
3562 but this is not possible with the current
3563 implementation. Also, we have to match
3564 collating symbols, which expand to more than
3565 one file, as a whole and not allow the
3566 individual bytes. */
3569 range_start = extra[idx];
3572 SET_LIST_BIT (extra[idx]);
3577 had_char_class = false;
3587 had_char_class = false;
3592 had_char_class = false;
3598 /* Discard any (non)matching list bytes that are all 0 at the
3599 end of the map. Decrease the map-length byte too. */
3600 while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
3609 if (syntax & RE_NO_BK_PARENS)
3616 if (syntax & RE_NO_BK_PARENS)
3623 if (syntax & RE_NEWLINE_ALT)
3630 if (syntax & RE_NO_BK_VBAR)
3637 if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
3638 goto handle_interval;
3644 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
3646 /* Do not translate the character after the \, so that we can
3647 distinguish, e.g., \B from \b, even if we normally would
3648 translate, e.g., B to b. */
3654 if (syntax & RE_NO_BK_PARENS)
3655 goto normal_backslash;
3661 if (COMPILE_STACK_FULL)
3663 RETALLOC (compile_stack.stack, compile_stack.size << 1,
3664 compile_stack_elt_t);
3665 if (compile_stack.stack == NULL) return REG_ESPACE;
3667 compile_stack.size <<= 1;
3670 /* These are the values to restore when we hit end of this
3671 group. They are all relative offsets, so that if the
3672 whole pattern moves because of realloc, they will still
3674 COMPILE_STACK_TOP.begalt_offset = begalt - COMPILED_BUFFER_VAR;
3675 COMPILE_STACK_TOP.fixup_alt_jump
3676 = fixup_alt_jump ? fixup_alt_jump - COMPILED_BUFFER_VAR + 1 : 0;
3677 COMPILE_STACK_TOP.laststart_offset = b - COMPILED_BUFFER_VAR;
3678 COMPILE_STACK_TOP.regnum = regnum;
3680 /* We will eventually replace the 0 with the number of
3681 groups inner to this one. But do not push a
3682 start_memory for groups beyond the last one we can
3683 represent in the compiled pattern. */
3684 if (regnum <= MAX_REGNUM)
3686 COMPILE_STACK_TOP.inner_group_offset = b
3687 - COMPILED_BUFFER_VAR + 2;
3688 BUF_PUSH_3 (start_memory, regnum, 0);
3691 compile_stack.avail++;
3696 /* If we've reached MAX_REGNUM groups, then this open
3697 won't actually generate any code, so we'll have to
3698 clear pending_exact explicitly. */
3704 if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
3706 if (COMPILE_STACK_EMPTY)
3708 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
3709 goto normal_backslash;
3711 FREE_STACK_RETURN (REG_ERPAREN);
3716 { /* Push a dummy failure point at the end of the
3717 alternative for a possible future
3718 `pop_failure_jump' to pop. See comments at
3719 `push_dummy_failure' in `re_match_2'. */
3720 BUF_PUSH (push_dummy_failure);
3722 /* We allocated space for this jump when we assigned
3723 to `fixup_alt_jump', in the `handle_alt' case below. */
3724 STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
3727 /* See similar code for backslashed left paren above. */
3728 if (COMPILE_STACK_EMPTY)
3730 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
3733 FREE_STACK_RETURN (REG_ERPAREN);
3736 /* Since we just checked for an empty stack above, this
3737 ``can't happen''. */
3738 assert (compile_stack.avail != 0);
3740 /* We don't just want to restore into `regnum', because
3741 later groups should continue to be numbered higher,
3742 as in `(ab)c(de)' -- the second group is #2. */
3743 regnum_t this_group_regnum;
3745 compile_stack.avail--;
3746 begalt = COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.begalt_offset;
3748 = COMPILE_STACK_TOP.fixup_alt_jump
3749 ? COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.fixup_alt_jump - 1
3751 laststart = COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.laststart_offset;
3752 this_group_regnum = COMPILE_STACK_TOP.regnum;
3753 /* If we've reached MAX_REGNUM groups, then this open
3754 won't actually generate any code, so we'll have to
3755 clear pending_exact explicitly. */
3758 /* We're at the end of the group, so now we know how many
3759 groups were inside this one. */
3760 if (this_group_regnum <= MAX_REGNUM)
3762 UCHAR_T *inner_group_loc
3763 = COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.inner_group_offset;
3765 *inner_group_loc = regnum - this_group_regnum;
3766 BUF_PUSH_3 (stop_memory, this_group_regnum,
3767 regnum - this_group_regnum);
3773 case '|': /* `\|'. */
3774 if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
3775 goto normal_backslash;
3777 if (syntax & RE_LIMITED_OPS)
3780 /* Insert before the previous alternative a jump which
3781 jumps to this alternative if the former fails. */
3782 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
3783 INSERT_JUMP (on_failure_jump, begalt,
3784 b + 2 + 2 * OFFSET_ADDRESS_SIZE);
3786 b += 1 + OFFSET_ADDRESS_SIZE;
3788 /* The alternative before this one has a jump after it
3789 which gets executed if it gets matched. Adjust that
3790 jump so it will jump to this alternative's analogous
3791 jump (put in below, which in turn will jump to the next
3792 (if any) alternative's such jump, etc.). The last such
3793 jump jumps to the correct final destination. A picture:
3799 If we are at `b', then fixup_alt_jump right now points to a
3800 three-byte space after `a'. We'll put in the jump, set
3801 fixup_alt_jump to right after `b', and leave behind three
3802 bytes which we'll fill in when we get to after `c'. */
3805 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
3807 /* Mark and leave space for a jump after this alternative,
3808 to be filled in later either by next alternative or
3809 when know we're at the end of a series of alternatives. */
3811 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
3812 b += 1 + OFFSET_ADDRESS_SIZE;
3820 /* If \{ is a literal. */
3821 if (!(syntax & RE_INTERVALS)
3822 /* If we're at `\{' and it's not the open-interval
3824 || (syntax & RE_NO_BK_BRACES))
3825 goto normal_backslash;
3829 /* If got here, then the syntax allows intervals. */
3831 /* At least (most) this many matches must be made. */
3832 int lower_bound = -1, upper_bound = -1;
3834 /* Place in the uncompiled pattern (i.e., just after
3835 the '{') to go back to if the interval is invalid. */
3836 const CHAR_T *beg_interval = p;
3839 goto invalid_interval;
3841 GET_UNSIGNED_NUMBER (lower_bound);
3845 GET_UNSIGNED_NUMBER (upper_bound);
3846 if (upper_bound < 0)
3847 upper_bound = RE_DUP_MAX;
3850 /* Interval such as `{1}' => match exactly once. */
3851 upper_bound = lower_bound;
3853 if (! (0 <= lower_bound && lower_bound <= upper_bound))
3854 goto invalid_interval;
3856 if (!(syntax & RE_NO_BK_BRACES))
3858 if (c != '\\' || p == pend)
3859 goto invalid_interval;
3864 goto invalid_interval;
3866 /* If it's invalid to have no preceding re. */
3869 if (syntax & RE_CONTEXT_INVALID_OPS
3870 && !(syntax & RE_INVALID_INTERVAL_ORD))
3871 FREE_STACK_RETURN (REG_BADRPT);
3872 else if (syntax & RE_CONTEXT_INDEP_OPS)
3875 goto unfetch_interval;
3878 /* We just parsed a valid interval. */
3880 if (RE_DUP_MAX < upper_bound)
3881 FREE_STACK_RETURN (REG_BADBR);
3883 /* If the upper bound is zero, don't want to succeed at
3884 all; jump from `laststart' to `b + 3', which will be
3885 the end of the buffer after we insert the jump. */
3886 /* ifdef WCHAR, 'b + 1 + OFFSET_ADDRESS_SIZE'
3887 instead of 'b + 3'. */
3888 if (upper_bound == 0)
3890 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
3891 INSERT_JUMP (jump, laststart, b + 1
3892 + OFFSET_ADDRESS_SIZE);
3893 b += 1 + OFFSET_ADDRESS_SIZE;
3896 /* Otherwise, we have a nontrivial interval. When
3897 we're all done, the pattern will look like:
3898 set_number_at <jump count> <upper bound>
3899 set_number_at <succeed_n count> <lower bound>
3900 succeed_n <after jump addr> <succeed_n count>
3902 jump_n <succeed_n addr> <jump count>
3903 (The upper bound and `jump_n' are omitted if
3904 `upper_bound' is 1, though.) */
3906 { /* If the upper bound is > 1, we need to insert
3907 more at the end of the loop. */
3908 unsigned nbytes = 2 + 4 * OFFSET_ADDRESS_SIZE +
3909 (upper_bound > 1) * (2 + 4 * OFFSET_ADDRESS_SIZE);
3911 GET_BUFFER_SPACE (nbytes);
3913 /* Initialize lower bound of the `succeed_n', even
3914 though it will be set during matching by its
3915 attendant `set_number_at' (inserted next),
3916 because `re_compile_fastmap' needs to know.
3917 Jump to the `jump_n' we might insert below. */
3918 INSERT_JUMP2 (succeed_n, laststart,
3919 b + 1 + 2 * OFFSET_ADDRESS_SIZE
3920 + (upper_bound > 1) * (1 + 2 * OFFSET_ADDRESS_SIZE)
3922 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
3924 /* Code to initialize the lower bound. Insert
3925 before the `succeed_n'. The `5' is the last two
3926 bytes of this `set_number_at', plus 3 bytes of
3927 the following `succeed_n'. */
3928 /* ifdef WCHAR, The '1+2*OFFSET_ADDRESS_SIZE'
3929 is the 'set_number_at', plus '1+OFFSET_ADDRESS_SIZE'
3930 of the following `succeed_n'. */
3931 PREFIX(insert_op2) (set_number_at, laststart, 1
3932 + 2 * OFFSET_ADDRESS_SIZE, lower_bound, b);
3933 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
3935 if (upper_bound > 1)
3936 { /* More than one repetition is allowed, so
3937 append a backward jump to the `succeed_n'
3938 that starts this interval.
3940 When we've reached this during matching,
3941 we'll have matched the interval once, so
3942 jump back only `upper_bound - 1' times. */
3943 STORE_JUMP2 (jump_n, b, laststart
3944 + 2 * OFFSET_ADDRESS_SIZE + 1,
3946 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
3948 /* The location we want to set is the second
3949 parameter of the `jump_n'; that is `b-2' as
3950 an absolute address. `laststart' will be
3951 the `set_number_at' we're about to insert;
3952 `laststart+3' the number to set, the source
3953 for the relative address. But we are
3954 inserting into the middle of the pattern --
3955 so everything is getting moved up by 5.
3956 Conclusion: (b - 2) - (laststart + 3) + 5,
3957 i.e., b - laststart.
3959 We insert this at the beginning of the loop
3960 so that if we fail during matching, we'll
3961 reinitialize the bounds. */
3962 PREFIX(insert_op2) (set_number_at, laststart,
3964 upper_bound - 1, b);
3965 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
3972 if (!(syntax & RE_INVALID_INTERVAL_ORD))
3973 FREE_STACK_RETURN (p == pend ? REG_EBRACE : REG_BADBR);
3975 /* Match the characters as literals. */
3978 if (syntax & RE_NO_BK_BRACES)
3981 goto normal_backslash;
3985 /* There is no way to specify the before_dot and after_dot
3986 operators. rms says this is ok. --karl */
3994 BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
4000 BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
4006 if (syntax & RE_NO_GNU_OPS)
4009 BUF_PUSH (wordchar);
4014 if (syntax & RE_NO_GNU_OPS)
4017 BUF_PUSH (notwordchar);
4022 if (syntax & RE_NO_GNU_OPS)
4028 if (syntax & RE_NO_GNU_OPS)
4034 if (syntax & RE_NO_GNU_OPS)
4036 BUF_PUSH (wordbound);
4040 if (syntax & RE_NO_GNU_OPS)
4042 BUF_PUSH (notwordbound);
4046 if (syntax & RE_NO_GNU_OPS)
4052 if (syntax & RE_NO_GNU_OPS)
4057 case '1': case '2': case '3': case '4': case '5':
4058 case '6': case '7': case '8': case '9':
4059 if (syntax & RE_NO_BK_REFS)
4065 FREE_STACK_RETURN (REG_ESUBREG);
4067 /* Can't back reference to a subexpression if inside of it. */
4068 if (group_in_compile_stack (compile_stack, (regnum_t) c1))
4072 BUF_PUSH_2 (duplicate, c1);
4078 if (syntax & RE_BK_PLUS_QM)
4081 goto normal_backslash;
4085 /* You might think it would be useful for \ to mean
4086 not to translate; but if we don't translate it
4087 it will never match anything. */
4095 /* Expects the character in `c'. */
4097 /* If no exactn currently being built. */
4100 /* If last exactn handle binary(or character) and
4101 new exactn handle character(or binary). */
4102 || is_exactn_bin != is_binary[p - 1 - pattern]
4105 /* If last exactn not at current position. */
4106 || pending_exact + *pending_exact + 1 != b
4108 /* We have only one byte following the exactn for the count. */
4109 || *pending_exact == (1 << BYTEWIDTH) - 1
4111 /* If followed by a repetition operator. */
4112 || *p == '*' || *p == '^'
4113 || ((syntax & RE_BK_PLUS_QM)
4114 ? *p == '\\' && (p[1] == '+' || p[1] == '?')
4115 : (*p == '+' || *p == '?'))
4116 || ((syntax & RE_INTERVALS)
4117 && ((syntax & RE_NO_BK_BRACES)
4119 : (p[0] == '\\' && p[1] == '{'))))
4121 /* Start building a new exactn. */
4126 /* Is this exactn binary data or character? */
4127 is_exactn_bin = is_binary[p - 1 - pattern];
4129 BUF_PUSH_2 (exactn_bin, 0);
4131 BUF_PUSH_2 (exactn, 0);
4133 BUF_PUSH_2 (exactn, 0);
4135 pending_exact = b - 1;
4142 } /* while p != pend */
4145 /* Through the pattern now. */
4148 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
4150 if (!COMPILE_STACK_EMPTY)
4151 FREE_STACK_RETURN (REG_EPAREN);
4153 /* If we don't want backtracking, force success
4154 the first time we reach the end of the compiled pattern. */
4155 if (syntax & RE_NO_POSIX_BACKTRACKING)
4163 free (compile_stack.stack);
4165 /* We have succeeded; set the length of the buffer. */
4167 bufp->used = (uintptr_t) b - (uintptr_t) COMPILED_BUFFER_VAR;
4169 bufp->used = b - bufp->buffer;
4175 DEBUG_PRINT1 ("\nCompiled pattern: \n");
4176 PREFIX(print_compiled_pattern) (bufp);
4180 #ifndef MATCH_MAY_ALLOCATE
4181 /* Initialize the failure stack to the largest possible stack. This
4182 isn't necessary unless we're trying to avoid calling alloca in
4183 the search and match routines. */
4185 int num_regs = bufp->re_nsub + 1;
4187 /* Since DOUBLE_FAIL_STACK refuses to double only if the current size
4188 is strictly greater than re_max_failures, the largest possible stack
4189 is 2 * re_max_failures failure points. */
4190 if (fail_stack.size < (2 * re_max_failures * MAX_FAILURE_ITEMS))
4192 fail_stack.size = (2 * re_max_failures * MAX_FAILURE_ITEMS);
4195 if (! fail_stack.stack)
4197 = (PREFIX(fail_stack_elt_t) *) xmalloc (fail_stack.size
4198 * sizeof (PREFIX(fail_stack_elt_t)));
4201 = (PREFIX(fail_stack_elt_t) *) xrealloc (fail_stack.stack,
4203 * sizeof (PREFIX(fail_stack_elt_t))));
4204 # else /* not emacs */
4205 if (! fail_stack.stack)
4207 = malloc (fail_stack.size * sizeof (PREFIX(fail_stack_elt_t)));
4210 = realloc (fail_stack.stack,
4211 fail_stack.size * sizeof (PREFIX(fail_stack_elt_t)));
4212 # endif /* not emacs */
4215 PREFIX(regex_grow_registers) (num_regs);
4217 #endif /* not MATCH_MAY_ALLOCATE */
4220 } /* regex_compile */
4222 /* Subroutines for `regex_compile'. */
4224 /* Store OP at LOC followed by two-byte integer parameter ARG. */
4225 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4228 PREFIX(store_op1) (re_opcode_t op, UCHAR_T *loc, int arg)
4230 *loc = (UCHAR_T) op;
4231 STORE_NUMBER (loc + 1, arg);
4235 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2. */
4236 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4239 PREFIX(store_op2) (re_opcode_t op, UCHAR_T *loc, int arg1, int arg2)
4241 *loc = (UCHAR_T) op;
4242 STORE_NUMBER (loc + 1, arg1);
4243 STORE_NUMBER (loc + 1 + OFFSET_ADDRESS_SIZE, arg2);
4247 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
4248 for OP followed by two-byte integer parameter ARG. */
4249 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4252 PREFIX(insert_op1) (re_opcode_t op, UCHAR_T *loc, int arg, UCHAR_T *end)
4254 register UCHAR_T *pfrom = end;
4255 register UCHAR_T *pto = end + 1 + OFFSET_ADDRESS_SIZE;
4257 while (pfrom != loc)
4260 PREFIX(store_op1) (op, loc, arg);
4264 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2. */
4265 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4268 PREFIX(insert_op2) (re_opcode_t op, UCHAR_T *loc, int arg1, int arg2,
4271 register UCHAR_T *pfrom = end;
4272 register UCHAR_T *pto = end + 1 + 2 * OFFSET_ADDRESS_SIZE;
4274 while (pfrom != loc)
4277 PREFIX(store_op2) (op, loc, arg1, arg2);
4281 /* P points to just after a ^ in PATTERN. Return true if that ^ comes
4282 after an alternative or a begin-subexpression. We assume there is at
4283 least one character before the ^. */
4286 PREFIX(at_begline_loc_p) (const CHAR_T *pattern, const CHAR_T *p,
4287 reg_syntax_t syntax)
4289 const CHAR_T *prev = p - 2;
4290 boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
4293 /* After a subexpression? */
4294 (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
4295 /* After an alternative? */
4296 || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
4300 /* The dual of at_begline_loc_p. This one is for $. We assume there is
4301 at least one character after the $, i.e., `P < PEND'. */
4304 PREFIX(at_endline_loc_p) (const CHAR_T *p, const CHAR_T *pend,
4305 reg_syntax_t syntax)
4307 const CHAR_T *next = p;
4308 boolean next_backslash = *next == '\\';
4309 const CHAR_T *next_next = p + 1 < pend ? p + 1 : 0;
4312 /* Before a subexpression? */
4313 (syntax & RE_NO_BK_PARENS ? *next == ')'
4314 : next_backslash && next_next && *next_next == ')')
4315 /* Before an alternative? */
4316 || (syntax & RE_NO_BK_VBAR ? *next == '|'
4317 : next_backslash && next_next && *next_next == '|');
4320 #else /* not INSIDE_RECURSION */
4322 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
4323 false if it's not. */
4326 group_in_compile_stack (compile_stack_type compile_stack,
4331 for (this_element = compile_stack.avail - 1;
4334 if (compile_stack.stack[this_element].regnum == regnum)
4339 #endif /* not INSIDE_RECURSION */
4341 #ifdef INSIDE_RECURSION
4344 /* This insert space, which size is "num", into the pattern at "loc".
4345 "end" must point the end of the allocated buffer. */
4347 insert_space (int num, CHAR_T *loc, CHAR_T *end)
4349 register CHAR_T *pto = end;
4350 register CHAR_T *pfrom = end - num;
4352 while (pfrom >= loc)
4358 static reg_errcode_t
4359 wcs_compile_range (CHAR_T range_start_char,
4360 const CHAR_T **p_ptr, const CHAR_T *pend,
4361 RE_TRANSLATE_TYPE translate, reg_syntax_t syntax,
4362 CHAR_T *b, CHAR_T *char_set)
4364 const CHAR_T *p = *p_ptr;
4365 CHAR_T range_start, range_end;
4369 uint32_t start_val, end_val;
4375 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4378 const char *collseq = (const char *) _NL_CURRENT(LC_COLLATE,
4379 _NL_COLLATE_COLLSEQWC);
4380 const unsigned char *extra = (const unsigned char *)
4381 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4383 if (range_start_char < -1)
4385 /* range_start is a collating symbol. */
4387 /* Retreive the index and get collation sequence value. */
4388 wextra = (int32_t*)(extra + char_set[-range_start_char]);
4389 start_val = wextra[1 + *wextra];
4392 start_val = collseq_table_lookup(collseq, TRANSLATE(range_start_char));
4394 end_val = collseq_table_lookup (collseq, TRANSLATE (p[0]));
4396 /* Report an error if the range is empty and the syntax prohibits
4398 ret = ((syntax & RE_NO_EMPTY_RANGES)
4399 && (start_val > end_val))? REG_ERANGE : REG_NOERROR;
4401 /* Insert space to the end of the char_ranges. */
4402 insert_space(2, b - char_set[5] - 2, b - 1);
4403 *(b - char_set[5] - 2) = (wchar_t)start_val;
4404 *(b - char_set[5] - 1) = (wchar_t)end_val;
4405 char_set[4]++; /* ranges_index */
4410 range_start = (range_start_char >= 0)? TRANSLATE (range_start_char):
4412 range_end = TRANSLATE (p[0]);
4413 /* Report an error if the range is empty and the syntax prohibits
4415 ret = ((syntax & RE_NO_EMPTY_RANGES)
4416 && (range_start > range_end))? REG_ERANGE : REG_NOERROR;
4418 /* Insert space to the end of the char_ranges. */
4419 insert_space(2, b - char_set[5] - 2, b - 1);
4420 *(b - char_set[5] - 2) = range_start;
4421 *(b - char_set[5] - 1) = range_end;
4422 char_set[4]++; /* ranges_index */
4424 /* Have to increment the pointer into the pattern string, so the
4425 caller isn't still at the ending character. */
4431 /* Read the ending character of a range (in a bracket expression) from the
4432 uncompiled pattern *P_PTR (which ends at PEND). We assume the
4433 starting character is in `P[-2]'. (`P[-1]' is the character `-'.)
4434 Then we set the translation of all bits between the starting and
4435 ending characters (inclusive) in the compiled pattern B.
4437 Return an error code.
4439 We use these short variable names so we can use the same macros as
4440 `regex_compile' itself. */
4442 static reg_errcode_t
4443 byte_compile_range (unsigned int range_start_char,
4444 const char **p_ptr, const char *pend,
4445 RE_TRANSLATE_TYPE translate, reg_syntax_t syntax,
4449 const char *p = *p_ptr;
4452 const unsigned char *collseq;
4453 unsigned int start_colseq;
4454 unsigned int end_colseq;
4462 /* Have to increment the pointer into the pattern string, so the
4463 caller isn't still at the ending character. */
4466 /* Report an error if the range is empty and the syntax prohibits this. */
4467 ret = syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
4470 collseq = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
4471 _NL_COLLATE_COLLSEQMB);
4473 start_colseq = collseq[(unsigned char) TRANSLATE (range_start_char)];
4474 end_colseq = collseq[(unsigned char) TRANSLATE (p[0])];
4475 for (this_char = 0; this_char <= (unsigned char) -1; ++this_char)
4477 unsigned int this_colseq = collseq[(unsigned char) TRANSLATE (this_char)];
4479 if (start_colseq <= this_colseq && this_colseq <= end_colseq)
4481 SET_LIST_BIT (TRANSLATE (this_char));
4486 /* Here we see why `this_char' has to be larger than an `unsigned
4487 char' -- we would otherwise go into an infinite loop, since all
4488 characters <= 0xff. */
4489 range_start_char = TRANSLATE (range_start_char);
4490 /* TRANSLATE(p[0]) is casted to char (not unsigned char) in TRANSLATE,
4491 and some compilers cast it to int implicitly, so following for_loop
4492 may fall to (almost) infinite loop.
4493 e.g. If translate[p[0]] = 0xff, end_char may equals to 0xffffffff.
4494 To avoid this, we cast p[0] to unsigned int and truncate it. */
4495 end_char = ((unsigned)TRANSLATE(p[0]) & ((1 << BYTEWIDTH) - 1));
4497 for (this_char = range_start_char; this_char <= end_char; ++this_char)
4499 SET_LIST_BIT (TRANSLATE (this_char));
4508 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
4509 BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible
4510 characters can start a string that matches the pattern. This fastmap
4511 is used by re_search to skip quickly over impossible starting points.
4513 The caller must supply the address of a (1 << BYTEWIDTH)-byte data
4514 area as BUFP->fastmap.
4516 We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
4519 Returns 0 if we succeed, -2 if an internal error. */
4522 /* local function for re_compile_fastmap.
4523 truncate wchar_t character to char. */
4525 static unsigned char
4526 truncate_wchar (CHAR_T c)
4528 unsigned char buf[MB_CUR_MAX];
4531 memset (&state, '\0', sizeof (state));
4532 retval = wcrtomb (buf, c, &state);
4533 return retval > 0 ? buf[0] : (unsigned char) c;
4538 PREFIX(re_compile_fastmap) (struct re_pattern_buffer *bufp)
4541 #ifdef MATCH_MAY_ALLOCATE
4542 PREFIX(fail_stack_type) fail_stack;
4544 #ifndef REGEX_MALLOC
4548 register char *fastmap = bufp->fastmap;
4551 /* We need to cast pattern to (wchar_t*), because we casted this compiled
4552 pattern to (char*) in regex_compile. */
4553 UCHAR_T *pattern = (UCHAR_T*)bufp->buffer;
4554 register UCHAR_T *pend = (UCHAR_T*) (bufp->buffer + bufp->used);
4556 UCHAR_T *pattern = bufp->buffer;
4557 register UCHAR_T *pend = pattern + bufp->used;
4559 UCHAR_T *p = pattern;
4562 /* This holds the pointer to the failure stack, when
4563 it is allocated relocatably. */
4564 fail_stack_elt_t *failure_stack_ptr;
4567 /* Assume that each path through the pattern can be null until
4568 proven otherwise. We set this false at the bottom of switch
4569 statement, to which we get only if a particular path doesn't
4570 match the empty string. */
4571 boolean path_can_be_null = true;
4573 /* We aren't doing a `succeed_n' to begin with. */
4574 boolean succeed_n_p = false;
4576 assert (fastmap != NULL && p != NULL);
4579 bzero (fastmap, 1 << BYTEWIDTH); /* Assume nothing's valid. */
4580 bufp->fastmap_accurate = 1; /* It will be when we're done. */
4581 bufp->can_be_null = 0;
4585 if (p == pend || *p == succeed)
4587 /* We have reached the (effective) end of pattern. */
4588 if (!FAIL_STACK_EMPTY ())
4590 bufp->can_be_null |= path_can_be_null;
4592 /* Reset for next path. */
4593 path_can_be_null = true;
4595 p = fail_stack.stack[--fail_stack.avail].pointer;
4603 /* We should never be about to go beyond the end of the pattern. */
4606 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
4609 /* I guess the idea here is to simply not bother with a fastmap
4610 if a backreference is used, since it's too hard to figure out
4611 the fastmap for the corresponding group. Setting
4612 `can_be_null' stops `re_search_2' from using the fastmap, so
4613 that is all we do. */
4615 bufp->can_be_null = 1;
4619 /* Following are the cases which match a character. These end
4624 fastmap[truncate_wchar(p[1])] = 1;
4638 /* It is hard to distinguish fastmap from (multi byte) characters
4639 which depends on current locale. */
4644 bufp->can_be_null = 1;
4648 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
4649 if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
4655 /* Chars beyond end of map must be allowed. */
4656 for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
4659 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
4660 if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
4666 for (j = 0; j < (1 << BYTEWIDTH); j++)
4667 if (SYNTAX (j) == Sword)
4673 for (j = 0; j < (1 << BYTEWIDTH); j++)
4674 if (SYNTAX (j) != Sword)
4681 int fastmap_newline = fastmap['\n'];
4683 /* `.' matches anything ... */
4684 for (j = 0; j < (1 << BYTEWIDTH); j++)
4687 /* ... except perhaps newline. */
4688 if (!(bufp->syntax & RE_DOT_NEWLINE))
4689 fastmap['\n'] = fastmap_newline;
4691 /* Return if we have already set `can_be_null'; if we have,
4692 then the fastmap is irrelevant. Something's wrong here. */
4693 else if (bufp->can_be_null)
4696 /* Otherwise, have to check alternative paths. */
4703 for (j = 0; j < (1 << BYTEWIDTH); j++)
4704 if (SYNTAX (j) == (enum syntaxcode) k)
4711 for (j = 0; j < (1 << BYTEWIDTH); j++)
4712 if (SYNTAX (j) != (enum syntaxcode) k)
4717 /* All cases after this match the empty string. These end with
4737 case push_dummy_failure:
4742 case pop_failure_jump:
4743 case maybe_pop_jump:
4746 case dummy_failure_jump:
4747 EXTRACT_NUMBER_AND_INCR (j, p);
4752 /* Jump backward implies we just went through the body of a
4753 loop and matched nothing. Opcode jumped to should be
4754 `on_failure_jump' or `succeed_n'. Just treat it like an
4755 ordinary jump. For a * loop, it has pushed its failure
4756 point already; if so, discard that as redundant. */
4757 if ((re_opcode_t) *p != on_failure_jump
4758 && (re_opcode_t) *p != succeed_n)
4762 EXTRACT_NUMBER_AND_INCR (j, p);
4765 /* If what's on the stack is where we are now, pop it. */
4766 if (!FAIL_STACK_EMPTY ()
4767 && fail_stack.stack[fail_stack.avail - 1].pointer == p)
4773 case on_failure_jump:
4774 case on_failure_keep_string_jump:
4775 handle_on_failure_jump:
4776 EXTRACT_NUMBER_AND_INCR (j, p);
4778 /* For some patterns, e.g., `(a?)?', `p+j' here points to the
4779 end of the pattern. We don't want to push such a point,
4780 since when we restore it above, entering the switch will
4781 increment `p' past the end of the pattern. We don't need
4782 to push such a point since we obviously won't find any more
4783 fastmap entries beyond `pend'. Such a pattern can match
4784 the null string, though. */
4787 if (!PUSH_PATTERN_OP (p + j, fail_stack))
4789 RESET_FAIL_STACK ();
4794 bufp->can_be_null = 1;
4798 EXTRACT_NUMBER_AND_INCR (k, p); /* Skip the n. */
4799 succeed_n_p = false;
4806 /* Get to the number of times to succeed. */
4807 p += OFFSET_ADDRESS_SIZE;
4809 /* Increment p past the n for when k != 0. */
4810 EXTRACT_NUMBER_AND_INCR (k, p);
4813 p -= 2 * OFFSET_ADDRESS_SIZE;
4814 succeed_n_p = true; /* Spaghetti code alert. */
4815 goto handle_on_failure_jump;
4821 p += 2 * OFFSET_ADDRESS_SIZE;
4832 abort (); /* We have listed all the cases. */
4835 /* Getting here means we have found the possible starting
4836 characters for one path of the pattern -- and that the empty
4837 string does not match. We need not follow this path further.
4838 Instead, look at the next alternative (remembered on the
4839 stack), or quit if no more. The test at the top of the loop
4840 does these things. */
4841 path_can_be_null = false;
4845 /* Set `can_be_null' for the last path (also the first path, if the
4846 pattern is empty). */
4847 bufp->can_be_null |= path_can_be_null;
4850 RESET_FAIL_STACK ();
4854 #else /* not INSIDE_RECURSION */
4857 re_compile_fastmap (struct re_pattern_buffer *bufp)
4860 if (MB_CUR_MAX != 1)
4861 return wcs_re_compile_fastmap(bufp);
4864 return byte_re_compile_fastmap(bufp);
4865 } /* re_compile_fastmap */
4867 weak_alias (__re_compile_fastmap, re_compile_fastmap)
4871 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
4872 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
4873 this memory for recording register information. STARTS and ENDS
4874 must be allocated using the malloc library routine, and must each
4875 be at least NUM_REGS * sizeof (regoff_t) bytes long.
4877 If NUM_REGS == 0, then subsequent matches should allocate their own
4880 Unless this function is called, the first search or match using
4881 PATTERN_BUFFER will allocate its own register data, without
4882 freeing the old data. */
4885 re_set_registers (struct re_pattern_buffer *bufp,
4886 struct re_registers *regs,
4887 unsigned int num_regs,
4888 regoff_t *starts, regoff_t *ends)
4892 bufp->regs_allocated = REGS_REALLOCATE;
4893 regs->num_regs = num_regs;
4894 regs->start = starts;
4899 bufp->regs_allocated = REGS_UNALLOCATED;
4901 regs->start = regs->end = (regoff_t *) 0;
4905 weak_alias (__re_set_registers, re_set_registers)
4908 /* Searching routines. */
4910 /* Like re_search_2, below, but only one string is specified, and
4911 doesn't let you say where to stop matching. */
4914 re_search (struct re_pattern_buffer *bufp,
4916 int size, int startpos, int range,
4917 struct re_registers *regs)
4919 return re_search_2 (bufp, NULL, 0, string, size, startpos, range,
4923 weak_alias (__re_search, re_search)
4927 /* Using the compiled pattern in BUFP->buffer, first tries to match the
4928 virtual concatenation of STRING1 and STRING2, starting first at index
4929 STARTPOS, then at STARTPOS + 1, and so on.
4931 STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
4933 RANGE is how far to scan while trying to match. RANGE = 0 means try
4934 only at STARTPOS; in general, the last start tried is STARTPOS +
4937 In REGS, return the indices of the virtual concatenation of STRING1
4938 and STRING2 that matched the entire BUFP->buffer and its contained
4941 Do not consider matching one past the index STOP in the virtual
4942 concatenation of STRING1 and STRING2.
4944 We return either the position in the strings at which the match was
4945 found, -1 if no match, or -2 if error (such as failure
4949 re_search_2 (struct re_pattern_buffer *bufp,
4950 const char *string1, int size1,
4951 const char *string2, int size2,
4952 int startpos, int range,
4953 struct re_registers *regs,
4957 if (MB_CUR_MAX != 1)
4958 return wcs_re_search_2 (bufp, string1, size1, string2, size2, startpos,
4962 return byte_re_search_2 (bufp, string1, size1, string2, size2, startpos,
4966 weak_alias (__re_search_2, re_search_2)
4969 #endif /* not INSIDE_RECURSION */
4971 #ifdef INSIDE_RECURSION
4973 #ifdef MATCH_MAY_ALLOCATE
4974 # define FREE_VAR(var) if (var) REGEX_FREE (var); var = NULL
4976 # define FREE_VAR(var) if (var) free (var); var = NULL
4980 # define MAX_ALLOCA_SIZE 2000
4982 # define FREE_WCS_BUFFERS() \
4984 if (size1 > MAX_ALLOCA_SIZE) \
4986 free (wcs_string1); \
4987 free (mbs_offset1); \
4991 FREE_VAR (wcs_string1); \
4992 FREE_VAR (mbs_offset1); \
4994 if (size2 > MAX_ALLOCA_SIZE) \
4996 free (wcs_string2); \
4997 free (mbs_offset2); \
5001 FREE_VAR (wcs_string2); \
5002 FREE_VAR (mbs_offset2); \
5010 PREFIX(re_search_2) (struct re_pattern_buffer *bufp,
5011 const char *string1, int size1,
5012 const char *string2, int size2,
5013 int startpos, int range,
5014 struct re_registers *regs,
5018 register char *fastmap = bufp->fastmap;
5019 register RE_TRANSLATE_TYPE translate = bufp->translate;
5020 int total_size = size1 + size2;
5021 int endpos = startpos + range;
5023 /* We need wchar_t* buffers correspond to cstring1, cstring2. */
5024 wchar_t *wcs_string1 = NULL, *wcs_string2 = NULL;
5025 /* We need the size of wchar_t buffers correspond to csize1, csize2. */
5026 int wcs_size1 = 0, wcs_size2 = 0;
5027 /* offset buffer for optimizatoin. See convert_mbs_to_wc. */
5028 int *mbs_offset1 = NULL, *mbs_offset2 = NULL;
5029 /* They hold whether each wchar_t is binary data or not. */
5030 char *is_binary = NULL;
5033 /* Check for out-of-range STARTPOS. */
5034 if (startpos < 0 || startpos > total_size)
5037 /* Fix up RANGE if it might eventually take us outside
5038 the virtual concatenation of STRING1 and STRING2.
5039 Make sure we won't move STARTPOS below 0 or above TOTAL_SIZE. */
5041 range = 0 - startpos;
5042 else if (endpos > total_size)
5043 range = total_size - startpos;
5045 /* If the search isn't to be a backwards one, don't waste time in a
5046 search for a pattern that must be anchored. */
5047 if (bufp->used > 0 && range > 0
5048 && ((re_opcode_t) bufp->buffer[0] == begbuf
5049 /* `begline' is like `begbuf' if it cannot match at newlines. */
5050 || ((re_opcode_t) bufp->buffer[0] == begline
5051 && !bufp->newline_anchor)))
5060 /* In a forward search for something that starts with \=.
5061 don't keep searching past point. */
5062 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == at_dot && range > 0)
5064 range = PT - startpos;
5070 /* Update the fastmap now if not correct already. */
5071 if (fastmap && !bufp->fastmap_accurate)
5072 if (re_compile_fastmap (bufp) == -2)
5076 /* Allocate wchar_t array for wcs_string1 and wcs_string2 and
5077 fill them with converted string. */
5080 if (size1 > MAX_ALLOCA_SIZE)
5082 wcs_string1 = TALLOC (size1 + 1, CHAR_T);
5083 mbs_offset1 = TALLOC (size1 + 1, int);
5084 is_binary = TALLOC (size1 + 1, char);
5088 wcs_string1 = REGEX_TALLOC (size1 + 1, CHAR_T);
5089 mbs_offset1 = REGEX_TALLOC (size1 + 1, int);
5090 is_binary = REGEX_TALLOC (size1 + 1, char);
5092 if (!wcs_string1 || !mbs_offset1 || !is_binary)
5094 if (size1 > MAX_ALLOCA_SIZE)
5102 FREE_VAR (wcs_string1);
5103 FREE_VAR (mbs_offset1);
5104 FREE_VAR (is_binary);
5108 wcs_size1 = convert_mbs_to_wcs(wcs_string1, string1, size1,
5109 mbs_offset1, is_binary);
5110 wcs_string1[wcs_size1] = L'\0'; /* for a sentinel */
5111 if (size1 > MAX_ALLOCA_SIZE)
5114 FREE_VAR (is_binary);
5118 if (size2 > MAX_ALLOCA_SIZE)
5120 wcs_string2 = TALLOC (size2 + 1, CHAR_T);
5121 mbs_offset2 = TALLOC (size2 + 1, int);
5122 is_binary = TALLOC (size2 + 1, char);
5126 wcs_string2 = REGEX_TALLOC (size2 + 1, CHAR_T);
5127 mbs_offset2 = REGEX_TALLOC (size2 + 1, int);
5128 is_binary = REGEX_TALLOC (size2 + 1, char);
5130 if (!wcs_string2 || !mbs_offset2 || !is_binary)
5132 FREE_WCS_BUFFERS ();
5133 if (size2 > MAX_ALLOCA_SIZE)
5136 FREE_VAR (is_binary);
5139 wcs_size2 = convert_mbs_to_wcs(wcs_string2, string2, size2,
5140 mbs_offset2, is_binary);
5141 wcs_string2[wcs_size2] = L'\0'; /* for a sentinel */
5142 if (size2 > MAX_ALLOCA_SIZE)
5145 FREE_VAR (is_binary);
5150 /* Loop through the string, looking for a place to start matching. */
5153 /* If a fastmap is supplied, skip quickly over characters that
5154 cannot be the start of a match. If the pattern can match the
5155 null string, however, we don't need to skip characters; we want
5156 the first null string. */
5157 if (fastmap && startpos < total_size && !bufp->can_be_null)
5159 if (range > 0) /* Searching forwards. */
5161 register const char *d;
5162 register int lim = 0;
5165 if (startpos < size1 && startpos + range >= size1)
5166 lim = range - (size1 - startpos);
5168 d = (startpos >= size1 ? string2 - size1 : string1) + startpos;
5170 /* Written out as an if-else to avoid testing `translate'
5174 && !fastmap[(unsigned char)
5175 translate[(unsigned char) *d++]])
5178 while (range > lim && !fastmap[(unsigned char) *d++])
5181 startpos += irange - range;
5183 else /* Searching backwards. */
5185 register CHAR_T c = (size1 == 0 || startpos >= size1
5186 ? string2[startpos - size1]
5187 : string1[startpos]);
5189 if (!fastmap[(unsigned char) TRANSLATE (c)])
5194 /* If can't match the null string, and that's all we have left, fail. */
5195 if (range >= 0 && startpos == total_size && fastmap
5196 && !bufp->can_be_null)
5199 FREE_WCS_BUFFERS ();
5205 val = wcs_re_match_2_internal (bufp, string1, size1, string2,
5206 size2, startpos, regs, stop,
5207 wcs_string1, wcs_size1,
5208 wcs_string2, wcs_size2,
5209 mbs_offset1, mbs_offset2);
5211 val = byte_re_match_2_internal (bufp, string1, size1, string2,
5212 size2, startpos, regs, stop);
5215 #ifndef REGEX_MALLOC
5224 FREE_WCS_BUFFERS ();
5232 FREE_WCS_BUFFERS ();
5252 FREE_WCS_BUFFERS ();
5258 /* This converts PTR, a pointer into one of the search wchar_t strings
5259 `string1' and `string2' into an multibyte string offset from the
5260 beginning of that string. We use mbs_offset to optimize.
5261 See convert_mbs_to_wcs. */
5262 # define POINTER_TO_OFFSET(ptr) \
5263 (FIRST_STRING_P (ptr) \
5264 ? ((regoff_t)(mbs_offset1 != NULL? mbs_offset1[(ptr)-string1] : 0)) \
5265 : ((regoff_t)((mbs_offset2 != NULL? mbs_offset2[(ptr)-string2] : 0) \
5268 /* This converts PTR, a pointer into one of the search strings `string1'
5269 and `string2' into an offset from the beginning of that string. */
5270 # define POINTER_TO_OFFSET(ptr) \
5271 (FIRST_STRING_P (ptr) \
5272 ? ((regoff_t) ((ptr) - string1)) \
5273 : ((regoff_t) ((ptr) - string2 + size1)))
5276 /* Macros for dealing with the split strings in re_match_2. */
5278 #define MATCHING_IN_FIRST_STRING (dend == end_match_1)
5280 /* Call before fetching a character with *d. This switches over to
5281 string2 if necessary. */
5282 #define PREFETCH() \
5285 /* End of string2 => fail. */ \
5286 if (dend == end_match_2) \
5288 /* End of string1 => advance to string2. */ \
5290 dend = end_match_2; \
5293 /* Test if at very beginning or at very end of the virtual concatenation
5294 of `string1' and `string2'. If only one string, it's `string2'. */
5295 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
5296 #define AT_STRINGS_END(d) ((d) == end2)
5299 /* Test if D points to a character which is word-constituent. We have
5300 two special cases to check for: if past the end of string1, look at
5301 the first character in string2; and if before the beginning of
5302 string2, look at the last character in string1. */
5304 /* Use internationalized API instead of SYNTAX. */
5305 # define WORDCHAR_P(d) \
5306 (iswalnum ((wint_t)((d) == end1 ? *string2 \
5307 : (d) == string2 - 1 ? *(end1 - 1) : *(d))) != 0 \
5308 || ((d) == end1 ? *string2 \
5309 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) == L'_')
5311 # define WORDCHAR_P(d) \
5312 (SYNTAX ((d) == end1 ? *string2 \
5313 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) \
5317 /* Disabled due to a compiler bug -- see comment at case wordbound */
5319 /* Test if the character before D and the one at D differ with respect
5320 to being word-constituent. */
5321 #define AT_WORD_BOUNDARY(d) \
5322 (AT_STRINGS_BEG (d) || AT_STRINGS_END (d) \
5323 || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
5326 /* Free everything we malloc. */
5327 #ifdef MATCH_MAY_ALLOCATE
5329 # define FREE_VARIABLES() \
5331 REGEX_FREE_STACK (fail_stack.stack); \
5332 FREE_VAR (regstart); \
5333 FREE_VAR (regend); \
5334 FREE_VAR (old_regstart); \
5335 FREE_VAR (old_regend); \
5336 FREE_VAR (best_regstart); \
5337 FREE_VAR (best_regend); \
5338 FREE_VAR (reg_info); \
5339 FREE_VAR (reg_dummy); \
5340 FREE_VAR (reg_info_dummy); \
5341 if (!cant_free_wcs_buf) \
5343 FREE_VAR (string1); \
5344 FREE_VAR (string2); \
5345 FREE_VAR (mbs_offset1); \
5346 FREE_VAR (mbs_offset2); \
5350 # define FREE_VARIABLES() \
5352 REGEX_FREE_STACK (fail_stack.stack); \
5353 FREE_VAR (regstart); \
5354 FREE_VAR (regend); \
5355 FREE_VAR (old_regstart); \
5356 FREE_VAR (old_regend); \
5357 FREE_VAR (best_regstart); \
5358 FREE_VAR (best_regend); \
5359 FREE_VAR (reg_info); \
5360 FREE_VAR (reg_dummy); \
5361 FREE_VAR (reg_info_dummy); \
5366 # define FREE_VARIABLES() \
5368 if (!cant_free_wcs_buf) \
5370 FREE_VAR (string1); \
5371 FREE_VAR (string2); \
5372 FREE_VAR (mbs_offset1); \
5373 FREE_VAR (mbs_offset2); \
5377 # define FREE_VARIABLES() ((void)0) /* Do nothing! But inhibit gcc warning. */
5379 #endif /* not MATCH_MAY_ALLOCATE */
5381 /* These values must meet several constraints. They must not be valid
5382 register values; since we have a limit of 255 registers (because
5383 we use only one byte in the pattern for the register number), we can
5384 use numbers larger than 255. They must differ by 1, because of
5385 NUM_FAILURE_ITEMS above. And the value for the lowest register must
5386 be larger than the value for the highest register, so we do not try
5387 to actually save any registers when none are active. */
5388 #define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
5389 #define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
5391 #else /* not INSIDE_RECURSION */
5392 /* Matching routines. */
5394 #ifndef emacs /* Emacs never uses this. */
5395 /* re_match is like re_match_2 except it takes only a single string. */
5398 re_match (struct re_pattern_buffer *bufp,
5401 struct re_registers *regs)
5405 if (MB_CUR_MAX != 1)
5406 result = wcs_re_match_2_internal (bufp, NULL, 0, string, size,
5408 NULL, 0, NULL, 0, NULL, NULL);
5411 result = byte_re_match_2_internal (bufp, NULL, 0, string, size,
5413 # ifndef REGEX_MALLOC
5421 weak_alias (__re_match, re_match)
5423 #endif /* not emacs */
5425 #endif /* not INSIDE_RECURSION */
5427 #ifdef INSIDE_RECURSION
5428 static boolean PREFIX(group_match_null_string_p) (UCHAR_T **p,
5430 PREFIX(register_info_type) *reg_info);
5431 static boolean PREFIX(alt_match_null_string_p) (UCHAR_T *p,
5433 PREFIX(register_info_type) *reg_info);
5434 static boolean PREFIX(common_op_match_null_string_p) (UCHAR_T **p,
5436 PREFIX(register_info_type) *reg_info);
5437 static int PREFIX(bcmp_translate) (const CHAR_T *s1, const CHAR_T *s2,
5438 int len, char *translate);
5439 #else /* not INSIDE_RECURSION */
5441 /* re_match_2 matches the compiled pattern in BUFP against the
5442 the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
5443 and SIZE2, respectively). We start matching at POS, and stop
5446 If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
5447 store offsets for the substring each group matched in REGS. See the
5448 documentation for exactly how many groups we fill.
5450 We return -1 if no match, -2 if an internal error (such as the
5451 failure stack overflowing). Otherwise, we return the length of the
5452 matched substring. */
5455 re_match_2 (struct re_pattern_buffer *bufp,
5456 const char *string1, int size1,
5457 const char *string2, int size2,
5458 int pos, struct re_registers *regs,
5463 if (MB_CUR_MAX != 1)
5464 result = wcs_re_match_2_internal (bufp, string1, size1, string2, size2,
5466 NULL, 0, NULL, 0, NULL, NULL);
5469 result = byte_re_match_2_internal (bufp, string1, size1, string2, size2,
5472 #ifndef REGEX_MALLOC
5480 weak_alias (__re_match_2, re_match_2)
5483 #endif /* not INSIDE_RECURSION */
5485 #ifdef INSIDE_RECURSION
5489 /* This check the substring (from 0, to length) of the multibyte string,
5490 to which offset_buffer correspond. And count how many wchar_t_characters
5491 the substring occupy. We use offset_buffer to optimization.
5492 See convert_mbs_to_wcs. */
5495 count_mbs_length (int *offset_buffer, int length)
5499 /* Check whether the size is valid. */
5503 if (offset_buffer == NULL)
5506 /* If there are no multibyte character, offset_buffer[i] == i.
5507 Optmize for this case. */
5508 if (offset_buffer[length] == length)
5511 /* Set up upper with length. (because for all i, offset_buffer[i] >= i) */
5517 int middle = (lower + upper) / 2;
5518 if (middle == lower || middle == upper)
5520 if (offset_buffer[middle] > length)
5522 else if (offset_buffer[middle] < length)
5532 /* This is a separate function so that we can force an alloca cleanup
5536 wcs_re_match_2_internal (struct re_pattern_buffer *bufp,
5537 const char *cstring1, int csize1,
5538 const char *cstring2, int csize2,
5540 struct re_registers *regs,
5542 /* string1 == string2 == NULL means
5543 string1/2, size1/2 and mbs_offset1/2 need
5544 setting up in this function. */
5545 /* We need wchar_t * buffers corresponding to
5546 cstring1, cstring2. */
5547 wchar_t *string1, int size1,
5548 wchar_t *string2, int size2,
5549 /* Offset buffer for optimization. See
5550 convert_mbs_to_wc. */
5555 byte_re_match_2_internal (struct re_pattern_buffer *bufp,
5556 const char *string1, int size1,
5557 const char *string2, int size2,
5559 struct re_registers *regs,
5563 /* General temporaries. */
5567 /* They hold whether each wchar_t is binary data or not. */
5568 char *is_binary = NULL;
5569 /* If true, we can't free string1/2, mbs_offset1/2. */
5570 int cant_free_wcs_buf = 1;
5573 /* Just past the end of the corresponding string. */
5574 const CHAR_T *end1, *end2;
5576 /* Pointers into string1 and string2, just past the last characters in
5577 each to consider matching. */
5578 const CHAR_T *end_match_1, *end_match_2;
5580 /* Where we are in the data, and the end of the current string. */
5581 const CHAR_T *d, *dend;
5583 /* Where we are in the pattern, and the end of the pattern. */
5585 UCHAR_T *pattern, *p;
5586 register UCHAR_T *pend;
5588 UCHAR_T *p = bufp->buffer;
5589 register UCHAR_T *pend = p + bufp->used;
5592 /* Mark the opcode just after a start_memory, so we can test for an
5593 empty subpattern when we get to the stop_memory. */
5594 UCHAR_T *just_past_start_mem = 0;
5596 /* We use this to map every character in the string. */
5597 RE_TRANSLATE_TYPE translate = bufp->translate;
5599 /* Failure point stack. Each place that can handle a failure further
5600 down the line pushes a failure point on this stack. It consists of
5601 restart, regend, and reg_info for all registers corresponding to
5602 the subexpressions we're currently inside, plus the number of such
5603 registers, and, finally, two char *'s. The first char * is where
5604 to resume scanning the pattern; the second one is where to resume
5605 scanning the strings. If the latter is zero, the failure point is
5606 a ``dummy''; if a failure happens and the failure point is a dummy,
5607 it gets discarded and the next next one is tried. */
5608 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
5609 PREFIX(fail_stack_type) fail_stack;
5612 static unsigned failure_id;
5613 unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0;
5617 /* This holds the pointer to the failure stack, when
5618 it is allocated relocatably. */
5619 fail_stack_elt_t *failure_stack_ptr;
5622 /* We fill all the registers internally, independent of what we
5623 return, for use in backreferences. The number here includes
5624 an element for register zero. */
5625 size_t num_regs = bufp->re_nsub + 1;
5627 /* The currently active registers. */
5628 active_reg_t lowest_active_reg = NO_LOWEST_ACTIVE_REG;
5629 active_reg_t highest_active_reg = NO_HIGHEST_ACTIVE_REG;
5631 /* Information on the contents of registers. These are pointers into
5632 the input strings; they record just what was matched (on this
5633 attempt) by a subexpression part of the pattern, that is, the
5634 regnum-th regstart pointer points to where in the pattern we began
5635 matching and the regnum-th regend points to right after where we
5636 stopped matching the regnum-th subexpression. (The zeroth register
5637 keeps track of what the whole pattern matches.) */
5638 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5639 const CHAR_T **regstart, **regend;
5642 /* If a group that's operated upon by a repetition operator fails to
5643 match anything, then the register for its start will need to be
5644 restored because it will have been set to wherever in the string we
5645 are when we last see its open-group operator. Similarly for a
5647 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5648 const CHAR_T **old_regstart, **old_regend;
5651 /* The is_active field of reg_info helps us keep track of which (possibly
5652 nested) subexpressions we are currently in. The matched_something
5653 field of reg_info[reg_num] helps us tell whether or not we have
5654 matched any of the pattern so far this time through the reg_num-th
5655 subexpression. These two fields get reset each time through any
5656 loop their register is in. */
5657 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
5658 PREFIX(register_info_type) *reg_info;
5661 /* The following record the register info as found in the above
5662 variables when we find a match better than any we've seen before.
5663 This happens as we backtrack through the failure points, which in
5664 turn happens only if we have not yet matched the entire string. */
5665 unsigned best_regs_set = false;
5666 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5667 const CHAR_T **best_regstart, **best_regend;
5670 /* Logically, this is `best_regend[0]'. But we don't want to have to
5671 allocate space for that if we're not allocating space for anything
5672 else (see below). Also, we never need info about register 0 for
5673 any of the other register vectors, and it seems rather a kludge to
5674 treat `best_regend' differently than the rest. So we keep track of
5675 the end of the best match so far in a separate variable. We
5676 initialize this to NULL so that when we backtrack the first time
5677 and need to test it, it's not garbage. */
5678 const CHAR_T *match_end = NULL;
5680 /* This helps SET_REGS_MATCHED avoid doing redundant work. */
5681 int set_regs_matched_done = 0;
5683 /* Used when we pop values we don't care about. */
5684 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5685 const CHAR_T **reg_dummy;
5686 PREFIX(register_info_type) *reg_info_dummy;
5690 /* Counts the total number of registers pushed. */
5691 unsigned num_regs_pushed = 0;
5694 /* Definitions for state transitions. More efficiently for gcc. */
5696 # if defined HAVE_SUBTRACT_LOCAL_LABELS && defined SHARED
5701 const void *__unbounded ptr; \
5702 offset = (p == pend \
5703 ? 0 : jmptable[SWITCH_ENUM_CAST ((re_opcode_t) *p++)]); \
5704 ptr = &&end_of_pattern + offset; \
5709 &&label_##x - &&end_of_pattern
5710 # define JUMP_TABLE_TYPE const int
5715 const void *__unbounded ptr; \
5716 ptr = (p == pend ? &&end_of_pattern \
5717 : jmptable[SWITCH_ENUM_CAST ((re_opcode_t) *p++)]); \
5723 # define JUMP_TABLE_TYPE const void *const
5725 # define CASE(x) label_##x
5726 static JUMP_TABLE_TYPE jmptable[] =
5745 REF (jump_past_alt),
5746 REF (on_failure_jump),
5747 REF (on_failure_keep_string_jump),
5748 REF (pop_failure_jump),
5749 REF (maybe_pop_jump),
5750 REF (dummy_failure_jump),
5751 REF (push_dummy_failure),
5754 REF (set_number_at),
5776 DEBUG_PRINT1 ("\n\nEntering re_match_2.\n");
5780 #ifdef MATCH_MAY_ALLOCATE
5781 /* Do not bother to initialize all the register variables if there are
5782 no groups in the pattern, as it takes a fair amount of time. If
5783 there are groups, we include space for register 0 (the whole
5784 pattern), even though we never use it, since it simplifies the
5785 array indexing. We should fix this. */
5788 regstart = REGEX_TALLOC (num_regs, const CHAR_T *);
5789 regend = REGEX_TALLOC (num_regs, const CHAR_T *);
5790 old_regstart = REGEX_TALLOC (num_regs, const CHAR_T *);
5791 old_regend = REGEX_TALLOC (num_regs, const CHAR_T *);
5792 best_regstart = REGEX_TALLOC (num_regs, const CHAR_T *);
5793 best_regend = REGEX_TALLOC (num_regs, const CHAR_T *);
5794 reg_info = REGEX_TALLOC (num_regs, PREFIX(register_info_type));
5795 reg_dummy = REGEX_TALLOC (num_regs, const CHAR_T *);
5796 reg_info_dummy = REGEX_TALLOC (num_regs, PREFIX(register_info_type));
5798 if (!(regstart && regend && old_regstart && old_regend && reg_info
5799 && best_regstart && best_regend && reg_dummy && reg_info_dummy))
5807 /* We must initialize all our variables to NULL, so that
5808 `FREE_VARIABLES' doesn't try to free them. */
5809 regstart = regend = old_regstart = old_regend = best_regstart
5810 = best_regend = reg_dummy = NULL;
5811 reg_info = reg_info_dummy = (PREFIX(register_info_type) *) NULL;
5813 #endif /* MATCH_MAY_ALLOCATE */
5815 /* The starting position is bogus. */
5817 if (pos < 0 || pos > csize1 + csize2)
5819 if (pos < 0 || pos > size1 + size2)
5827 /* Allocate wchar_t array for string1 and string2 and
5828 fill them with converted string. */
5829 if (string1 == NULL && string2 == NULL)
5831 /* We need seting up buffers here. */
5833 /* We must free wcs buffers in this function. */
5834 cant_free_wcs_buf = 0;
5838 string1 = REGEX_TALLOC (csize1 + 1, CHAR_T);
5839 mbs_offset1 = REGEX_TALLOC (csize1 + 1, int);
5840 is_binary = REGEX_TALLOC (csize1 + 1, char);
5841 if (!string1 || !mbs_offset1 || !is_binary)
5844 FREE_VAR (mbs_offset1);
5845 FREE_VAR (is_binary);
5851 string2 = REGEX_TALLOC (csize2 + 1, CHAR_T);
5852 mbs_offset2 = REGEX_TALLOC (csize2 + 1, int);
5853 is_binary = REGEX_TALLOC (csize2 + 1, char);
5854 if (!string2 || !mbs_offset2 || !is_binary)
5857 FREE_VAR (mbs_offset1);
5859 FREE_VAR (mbs_offset2);
5860 FREE_VAR (is_binary);
5863 size2 = convert_mbs_to_wcs(string2, cstring2, csize2,
5864 mbs_offset2, is_binary);
5865 string2[size2] = L'\0'; /* for a sentinel */
5866 FREE_VAR (is_binary);
5870 /* We need to cast pattern to (wchar_t*), because we casted this compiled
5871 pattern to (char*) in regex_compile. */
5872 p = pattern = (CHAR_T*)bufp->buffer;
5873 pend = (CHAR_T*)(bufp->buffer + bufp->used);
5877 /* Initialize subexpression text positions to -1 to mark ones that no
5878 start_memory/stop_memory has been seen for. Also initialize the
5879 register information struct. */
5880 for (mcnt = 1; (unsigned) mcnt < num_regs; mcnt++)
5882 regstart[mcnt] = regend[mcnt]
5883 = old_regstart[mcnt] = old_regend[mcnt] = REG_UNSET_VALUE;
5885 REG_MATCH_NULL_STRING_P (reg_info[mcnt]) = MATCH_NULL_UNSET_VALUE;
5886 IS_ACTIVE (reg_info[mcnt]) = 0;
5887 MATCHED_SOMETHING (reg_info[mcnt]) = 0;
5888 EVER_MATCHED_SOMETHING (reg_info[mcnt]) = 0;
5891 /* We move `string1' into `string2' if the latter's empty -- but not if
5892 `string1' is null. */
5893 if (size2 == 0 && string1 != NULL)
5900 mbs_offset2 = mbs_offset1;
5906 end1 = string1 + size1;
5907 end2 = string2 + size2;
5909 /* Compute where to stop matching, within the two strings. */
5913 mcnt = count_mbs_length(mbs_offset1, stop);
5914 end_match_1 = string1 + mcnt;
5915 end_match_2 = string2;
5919 if (stop > csize1 + csize2)
5920 stop = csize1 + csize2;
5922 mcnt = count_mbs_length(mbs_offset2, stop-csize1);
5923 end_match_2 = string2 + mcnt;
5926 { /* count_mbs_length return error. */
5933 end_match_1 = string1 + stop;
5934 end_match_2 = string2;
5939 end_match_2 = string2 + stop - size1;
5943 /* `p' scans through the pattern as `d' scans through the data.
5944 `dend' is the end of the input string that `d' points within. `d'
5945 is advanced into the following input string whenever necessary, but
5946 this happens before fetching; therefore, at the beginning of the
5947 loop, `d' can be pointing at the end of a string, but it cannot
5950 if (size1 > 0 && pos <= csize1)
5952 mcnt = count_mbs_length(mbs_offset1, pos);
5958 mcnt = count_mbs_length(mbs_offset2, pos-csize1);
5964 { /* count_mbs_length return error. */
5969 if (size1 > 0 && pos <= size1)
5976 d = string2 + pos - size1;
5981 DEBUG_PRINT1 ("The compiled pattern is:\n");
5982 DEBUG_PRINT_COMPILED_PATTERN (bufp, p, pend);
5983 DEBUG_PRINT1 ("The string to match is: `");
5984 DEBUG_PRINT_DOUBLE_STRING (d, string1, size1, string2, size2);
5985 DEBUG_PRINT1 ("'\n");
5987 /* This loops over pattern commands. It exits by returning from the
5988 function if the match is complete, or it drops through if the match
5989 fails at this starting point in the input data. */
5993 DEBUG_PRINT2 ("\n%p: ", p);
5995 DEBUG_PRINT2 ("\n0x%x: ", p);
6007 /* End of pattern means we might have succeeded. */
6008 DEBUG_PRINT1 ("end of pattern ... ");
6010 /* If we haven't matched the entire string, and we want the
6011 longest match, try backtracking. */
6012 if (d != end_match_2)
6014 /* 1 if this match is the best seen so far. */
6015 boolean best_match_p;
6018 /* 1 if this match ends in the same string (string1 or string2)
6019 as the best previous match. */
6020 boolean same_str_p = (FIRST_STRING_P (match_end)
6021 == MATCHING_IN_FIRST_STRING);
6023 /* AIX compiler got confused when this was combined
6024 with the previous declaration. */
6026 best_match_p = d > match_end;
6028 best_match_p = !MATCHING_IN_FIRST_STRING;
6031 DEBUG_PRINT1 ("backtracking.\n");
6033 if (!FAIL_STACK_EMPTY ())
6034 { /* More failure points to try. */
6036 /* If exceeds best match so far, save it. */
6037 if (!best_regs_set || best_match_p)
6039 best_regs_set = true;
6042 DEBUG_PRINT1 ("\nSAVING match as best so far.\n");
6044 for (mcnt = 1; (unsigned) mcnt < num_regs; mcnt++)
6046 best_regstart[mcnt] = regstart[mcnt];
6047 best_regend[mcnt] = regend[mcnt];
6053 /* If no failure points, don't restore garbage. And if
6054 last match is real best match, don't restore second
6056 else if (best_regs_set && !best_match_p)
6059 /* Restore best match. It may happen that `dend ==
6060 end_match_1' while the restored d is in string2.
6061 For example, the pattern `x.*y.*z' against the
6062 strings `x-' and `y-z-', if the two strings are
6063 not consecutive in memory. */
6064 DEBUG_PRINT1 ("Restoring best registers.\n");
6067 dend = ((d >= string1 && d <= end1)
6068 ? end_match_1 : end_match_2);
6070 for (mcnt = 1; (unsigned) mcnt < num_regs; mcnt++)
6072 regstart[mcnt] = best_regstart[mcnt];
6073 regend[mcnt] = best_regend[mcnt];
6076 } /* d != end_match_2 */
6079 DEBUG_PRINT1 ("Accepting match.\n");
6080 /* If caller wants register contents data back, do it. */
6081 if (regs && !bufp->no_sub)
6083 /* Have the register data arrays been allocated? */
6084 if (bufp->regs_allocated == REGS_UNALLOCATED)
6085 { /* No. So allocate them with malloc. We need one
6086 extra element beyond `num_regs' for the `-1' marker
6088 regs->num_regs = MAX (RE_NREGS, num_regs + 1);
6089 regs->start = TALLOC (regs->num_regs, regoff_t);
6090 regs->end = TALLOC (regs->num_regs, regoff_t);
6091 if (regs->start == NULL || regs->end == NULL)
6096 bufp->regs_allocated = REGS_REALLOCATE;
6098 else if (bufp->regs_allocated == REGS_REALLOCATE)
6099 { /* Yes. If we need more elements than were already
6100 allocated, reallocate them. If we need fewer, just
6102 if (regs->num_regs < num_regs + 1)
6104 regs->num_regs = num_regs + 1;
6105 RETALLOC (regs->start, regs->num_regs, regoff_t);
6106 RETALLOC (regs->end, regs->num_regs, regoff_t);
6107 if (regs->start == NULL || regs->end == NULL)
6116 /* These braces fend off a "empty body in an else-statement"
6117 warning under GCC when assert expands to nothing. */
6118 assert (bufp->regs_allocated == REGS_FIXED);
6121 /* Convert the pointer data in `regstart' and `regend' to
6122 indices. Register zero has to be set differently,
6123 since we haven't kept track of any info for it. */
6124 if (regs->num_regs > 0)
6126 regs->start[0] = pos;
6128 if (MATCHING_IN_FIRST_STRING)
6129 regs->end[0] = (mbs_offset1 != NULL ?
6130 mbs_offset1[d-string1] : 0);
6132 regs->end[0] = csize1 + (mbs_offset2 != NULL
6133 ? mbs_offset2[d-string2] : 0);
6135 regs->end[0] = (MATCHING_IN_FIRST_STRING
6136 ? ((regoff_t) (d - string1))
6137 : ((regoff_t) (d - string2 + size1)));
6141 /* Go through the first `min (num_regs, regs->num_regs)'
6142 registers, since that is all we initialized. */
6143 for (mcnt = 1; (unsigned) mcnt < MIN (num_regs, regs->num_regs);
6146 if (REG_UNSET (regstart[mcnt]) || REG_UNSET (regend[mcnt]))
6147 regs->start[mcnt] = regs->end[mcnt] = -1;
6151 = (regoff_t) POINTER_TO_OFFSET (regstart[mcnt]);
6153 = (regoff_t) POINTER_TO_OFFSET (regend[mcnt]);
6157 /* If the regs structure we return has more elements than
6158 were in the pattern, set the extra elements to -1. If
6159 we (re)allocated the registers, this is the case,
6160 because we always allocate enough to have at least one
6162 for (mcnt = num_regs; (unsigned) mcnt < regs->num_regs; mcnt++)
6163 regs->start[mcnt] = regs->end[mcnt] = -1;
6164 } /* regs && !bufp->no_sub */
6166 DEBUG_PRINT4 ("%u failure points pushed, %u popped (%u remain).\n",
6167 nfailure_points_pushed, nfailure_points_popped,
6168 nfailure_points_pushed - nfailure_points_popped);
6169 DEBUG_PRINT2 ("%u registers pushed.\n", num_regs_pushed);
6172 if (MATCHING_IN_FIRST_STRING)
6173 mcnt = mbs_offset1 != NULL ? mbs_offset1[d-string1] : 0;
6175 mcnt = (mbs_offset2 != NULL ? mbs_offset2[d-string2] : 0) +
6179 mcnt = d - pos - (MATCHING_IN_FIRST_STRING
6180 ? string1 : string2 - size1);
6183 DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt);
6190 /* Otherwise match next pattern command. */
6191 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
6194 /* Ignore these. Used to ignore the n of succeed_n's which
6195 currently have n == 0. */
6197 DEBUG_PRINT1 ("EXECUTING no_op.\n");
6201 DEBUG_PRINT1 ("EXECUTING succeed.\n");
6204 /* Match the next n pattern characters exactly. The following
6205 byte in the pattern defines n, and the n bytes after that
6206 are the characters to match. */
6212 DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt);
6214 /* This is written out as an if-else so we don't waste time
6215 testing `translate' inside the loop. */
6224 if ((UCHAR_T) translate[(unsigned char) *d++]
6230 if (*d++ != (CHAR_T) *p++)
6234 if ((UCHAR_T) translate[(unsigned char) *d++]
6246 if (*d++ != (CHAR_T) *p++) goto fail;
6250 SET_REGS_MATCHED ();
6254 /* Match any character except possibly a newline or a null. */
6256 DEBUG_PRINT1 ("EXECUTING anychar.\n");
6260 if ((!(bufp->syntax & RE_DOT_NEWLINE) && TRANSLATE (*d) == '\n')
6261 || (bufp->syntax & RE_DOT_NOT_NULL && TRANSLATE (*d) == '\000'))
6264 SET_REGS_MATCHED ();
6265 DEBUG_PRINT2 (" Matched `%ld'.\n", (long int) *d);
6275 unsigned int i, char_class_length, coll_symbol_length,
6276 equiv_class_length, ranges_length, chars_length, length;
6277 CHAR_T *workp, *workp2, *charset_top;
6278 #define WORK_BUFFER_SIZE 128
6279 CHAR_T str_buf[WORK_BUFFER_SIZE];
6284 boolean negate = (re_opcode_t) *(p - 1) == charset_not;
6286 DEBUG_PRINT2 ("EXECUTING charset%s.\n", negate ? "_not" : "");
6288 c = TRANSLATE (*d); /* The character to match. */
6291 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
6293 charset_top = p - 1;
6294 char_class_length = *p++;
6295 coll_symbol_length = *p++;
6296 equiv_class_length = *p++;
6297 ranges_length = *p++;
6298 chars_length = *p++;
6299 /* p points charset[6], so the address of the next instruction
6300 (charset[l+m+n+2o+k+p']) equals p[l+m+n+2*o+p'],
6301 where l=length of char_classes, m=length of collating_symbol,
6302 n=equivalence_class, o=length of char_range,
6303 p'=length of character. */
6305 /* Update p to indicate the next instruction. */
6306 p += char_class_length + coll_symbol_length+ equiv_class_length +
6307 2*ranges_length + chars_length;
6309 /* match with char_class? */
6310 for (i = 0; i < char_class_length ; i += CHAR_CLASS_SIZE)
6313 uintptr_t alignedp = ((uintptr_t)workp
6314 + __alignof__(wctype_t) - 1)
6315 & ~(uintptr_t)(__alignof__(wctype_t) - 1);
6316 wctype = *((wctype_t*)alignedp);
6317 workp += CHAR_CLASS_SIZE;
6318 if (iswctype((wint_t)c, wctype))
6319 goto char_set_matched;
6322 /* match with collating_symbol? */
6326 const unsigned char *extra = (const unsigned char *)
6327 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
6329 for (workp2 = workp + coll_symbol_length ; workp < workp2 ;
6333 wextra = (int32_t*)(extra + *workp++);
6334 for (i = 0; i < *wextra; ++i)
6335 if (TRANSLATE(d[i]) != wextra[1 + i])
6340 /* Update d, however d will be incremented at
6341 char_set_matched:, we decrement d here. */
6343 goto char_set_matched;
6347 else /* (nrules == 0) */
6349 /* If we can't look up collation data, we use wcscoll
6352 for (workp2 = workp + coll_symbol_length ; workp < workp2 ;)
6354 const CHAR_T *backup_d = d, *backup_dend = dend;
6355 length = wcslen (workp);
6357 /* If wcscoll(the collating symbol, whole string) > 0,
6358 any substring of the string never match with the
6359 collating symbol. */
6360 if (wcscoll (workp, d) > 0)
6362 workp += length + 1;
6366 /* First, we compare the collating symbol with
6367 the first character of the string.
6368 If it don't match, we add the next character to
6369 the compare buffer in turn. */
6370 for (i = 0 ; i < WORK_BUFFER_SIZE-1 ; i++, d++)
6375 if (dend == end_match_2)
6381 /* add next character to the compare buffer. */
6382 str_buf[i] = TRANSLATE(*d);
6383 str_buf[i+1] = '\0';
6385 match = wcscoll (workp, str_buf);
6387 goto char_set_matched;
6390 /* (str_buf > workp) indicate (str_buf + X > workp),
6391 because for all X (str_buf + X > str_buf).
6392 So we don't need continue this loop. */
6395 /* Otherwise(str_buf < workp),
6396 (str_buf+next_character) may equals (workp).
6397 So we continue this loop. */
6402 workp += length + 1;
6405 /* match with equivalence_class? */
6409 const CHAR_T *backup_d = d, *backup_dend = dend;
6410 /* Try to match the equivalence class against
6411 those known to the collate implementation. */
6412 const int32_t *table;
6413 const int32_t *weights;
6414 const int32_t *extra;
6415 const int32_t *indirect;
6420 /* This #include defines a local function! */
6421 # include <locale/weightwc.h>
6423 table = (const int32_t *)
6424 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEWC);
6425 weights = (const wint_t *)
6426 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTWC);
6427 extra = (const wint_t *)
6428 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAWC);
6429 indirect = (const int32_t *)
6430 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTWC);
6432 /* Write 1 collating element to str_buf, and
6436 for (i = 0 ; idx2 == 0 && i < WORK_BUFFER_SIZE - 1; i++)
6438 cp = (wint_t*)str_buf;
6441 if (dend == end_match_2)
6446 str_buf[i] = TRANSLATE(*(d+i));
6447 str_buf[i+1] = '\0'; /* sentinel */
6448 idx2 = findidx ((const wint_t**)&cp);
6451 /* Update d, however d will be incremented at
6452 char_set_matched:, we decrement d here. */
6453 d = backup_d + ((wchar_t*)cp - (wchar_t*)str_buf - 1);
6456 if (dend == end_match_2)
6465 len = weights[idx2];
6467 for (workp2 = workp + equiv_class_length ; workp < workp2 ;
6470 idx = (int32_t)*workp;
6471 /* We already checked idx != 0 in regex_compile. */
6473 if (idx2 != 0 && len == weights[idx])
6476 while (cnt < len && (weights[idx + 1 + cnt]
6477 == weights[idx2 + 1 + cnt]))
6481 goto char_set_matched;
6488 else /* (nrules == 0) */
6490 /* If we can't look up collation data, we use wcscoll
6493 for (workp2 = workp + equiv_class_length ; workp < workp2 ;)
6495 const CHAR_T *backup_d = d, *backup_dend = dend;
6496 length = wcslen (workp);
6498 /* If wcscoll(the collating symbol, whole string) > 0,
6499 any substring of the string never match with the
6500 collating symbol. */
6501 if (wcscoll (workp, d) > 0)
6503 workp += length + 1;
6507 /* First, we compare the equivalence class with
6508 the first character of the string.
6509 If it don't match, we add the next character to
6510 the compare buffer in turn. */
6511 for (i = 0 ; i < WORK_BUFFER_SIZE - 1 ; i++, d++)
6516 if (dend == end_match_2)
6522 /* add next character to the compare buffer. */
6523 str_buf[i] = TRANSLATE(*d);
6524 str_buf[i+1] = '\0';
6526 match = wcscoll (workp, str_buf);
6529 goto char_set_matched;
6532 /* (str_buf > workp) indicate (str_buf + X > workp),
6533 because for all X (str_buf + X > str_buf).
6534 So we don't need continue this loop. */
6537 /* Otherwise(str_buf < workp),
6538 (str_buf+next_character) may equals (workp).
6539 So we continue this loop. */
6544 workp += length + 1;
6548 /* match with char_range? */
6552 uint32_t collseqval;
6553 const char *collseq = (const char *)
6554 _NL_CURRENT(LC_COLLATE, _NL_COLLATE_COLLSEQWC);
6556 collseqval = collseq_table_lookup (collseq, c);
6558 for (; workp < p - chars_length ;)
6560 uint32_t start_val, end_val;
6562 /* We already compute the collation sequence value
6563 of the characters (or collating symbols). */
6564 start_val = (uint32_t) *workp++; /* range_start */
6565 end_val = (uint32_t) *workp++; /* range_end */
6567 if (start_val <= collseqval && collseqval <= end_val)
6568 goto char_set_matched;
6574 /* We set range_start_char at str_buf[0], range_end_char
6575 at str_buf[4], and compared char at str_buf[2]. */
6580 for (; workp < p - chars_length ;)
6582 wchar_t *range_start_char, *range_end_char;
6584 /* match if (range_start_char <= c <= range_end_char). */
6586 /* If range_start(or end) < 0, we assume -range_start(end)
6587 is the offset of the collating symbol which is specified
6588 as the character of the range start(end). */
6592 range_start_char = charset_top - (*workp++);
6595 str_buf[0] = *workp++;
6596 range_start_char = str_buf;
6601 range_end_char = charset_top - (*workp++);
6604 str_buf[4] = *workp++;
6605 range_end_char = str_buf + 4;
6608 if (wcscoll (range_start_char, str_buf+2) <= 0
6609 && wcscoll (str_buf+2, range_end_char) <= 0)
6610 goto char_set_matched;
6614 /* match with char? */
6615 for (; workp < p ; workp++)
6617 goto char_set_matched;
6622 if (negate) goto fail;
6624 /* Cast to `unsigned' instead of `unsigned char' in case the
6625 bit list is a full 32 bytes long. */
6626 if (c < (unsigned) (*p * BYTEWIDTH)
6627 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
6632 if (!negate) goto fail;
6633 #undef WORK_BUFFER_SIZE
6635 SET_REGS_MATCHED ();
6641 /* The beginning of a group is represented by start_memory.
6642 The arguments are the register number in the next byte, and the
6643 number of groups inner to this one in the next. The text
6644 matched within the group is recorded (in the internal
6645 registers data structure) under the register number. */
6646 CASE (start_memory):
6647 DEBUG_PRINT3 ("EXECUTING start_memory %ld (%ld):\n",
6648 (long int) *p, (long int) p[1]);
6650 /* Find out if this group can match the empty string. */
6651 p1 = p; /* To send to group_match_null_string_p. */
6653 if (REG_MATCH_NULL_STRING_P (reg_info[*p]) == MATCH_NULL_UNSET_VALUE)
6654 REG_MATCH_NULL_STRING_P (reg_info[*p])
6655 = PREFIX(group_match_null_string_p) (&p1, pend, reg_info);
6657 /* Save the position in the string where we were the last time
6658 we were at this open-group operator in case the group is
6659 operated upon by a repetition operator, e.g., with `(a*)*b'
6660 against `ab'; then we want to ignore where we are now in
6661 the string in case this attempt to match fails. */
6662 old_regstart[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
6663 ? REG_UNSET (regstart[*p]) ? d : regstart[*p]
6665 DEBUG_PRINT2 (" old_regstart: %d\n",
6666 POINTER_TO_OFFSET (old_regstart[*p]));
6669 DEBUG_PRINT2 (" regstart: %d\n", POINTER_TO_OFFSET (regstart[*p]));
6671 IS_ACTIVE (reg_info[*p]) = 1;
6672 MATCHED_SOMETHING (reg_info[*p]) = 0;
6674 /* Clear this whenever we change the register activity status. */
6675 set_regs_matched_done = 0;
6677 /* This is the new highest active register. */
6678 highest_active_reg = *p;
6680 /* If nothing was active before, this is the new lowest active
6682 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
6683 lowest_active_reg = *p;
6685 /* Move past the register number and inner group count. */
6687 just_past_start_mem = p;
6692 /* The stop_memory opcode represents the end of a group. Its
6693 arguments are the same as start_memory's: the register
6694 number, and the number of inner groups. */
6696 DEBUG_PRINT3 ("EXECUTING stop_memory %ld (%ld):\n",
6697 (long int) *p, (long int) p[1]);
6699 /* We need to save the string position the last time we were at
6700 this close-group operator in case the group is operated
6701 upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
6702 against `aba'; then we want to ignore where we are now in
6703 the string in case this attempt to match fails. */
6704 old_regend[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
6705 ? REG_UNSET (regend[*p]) ? d : regend[*p]
6707 DEBUG_PRINT2 (" old_regend: %d\n",
6708 POINTER_TO_OFFSET (old_regend[*p]));
6711 DEBUG_PRINT2 (" regend: %d\n", POINTER_TO_OFFSET (regend[*p]));
6713 /* This register isn't active anymore. */
6714 IS_ACTIVE (reg_info[*p]) = 0;
6716 /* Clear this whenever we change the register activity status. */
6717 set_regs_matched_done = 0;
6719 /* If this was the only register active, nothing is active
6721 if (lowest_active_reg == highest_active_reg)
6723 lowest_active_reg = NO_LOWEST_ACTIVE_REG;
6724 highest_active_reg = NO_HIGHEST_ACTIVE_REG;
6727 { /* We must scan for the new highest active register, since
6728 it isn't necessarily one less than now: consider
6729 (a(b)c(d(e)f)g). When group 3 ends, after the f), the
6730 new highest active register is 1. */
6732 while (r > 0 && !IS_ACTIVE (reg_info[r]))
6735 /* If we end up at register zero, that means that we saved
6736 the registers as the result of an `on_failure_jump', not
6737 a `start_memory', and we jumped to past the innermost
6738 `stop_memory'. For example, in ((.)*) we save
6739 registers 1 and 2 as a result of the *, but when we pop
6740 back to the second ), we are at the stop_memory 1.
6741 Thus, nothing is active. */
6744 lowest_active_reg = NO_LOWEST_ACTIVE_REG;
6745 highest_active_reg = NO_HIGHEST_ACTIVE_REG;
6748 highest_active_reg = r;
6751 /* If just failed to match something this time around with a
6752 group that's operated on by a repetition operator, try to
6753 force exit from the ``loop'', and restore the register
6754 information for this group that we had before trying this
6756 if ((!MATCHED_SOMETHING (reg_info[*p])
6757 || just_past_start_mem == p - 1)
6760 boolean is_a_jump_n = false;
6764 switch ((re_opcode_t) *p1++)
6768 case pop_failure_jump:
6769 case maybe_pop_jump:
6771 case dummy_failure_jump:
6772 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
6774 p1 += OFFSET_ADDRESS_SIZE;
6782 /* If the next operation is a jump backwards in the pattern
6783 to an on_failure_jump right before the start_memory
6784 corresponding to this stop_memory, exit from the loop
6785 by forcing a failure after pushing on the stack the
6786 on_failure_jump's jump in the pattern, and d. */
6787 if (mcnt < 0 && (re_opcode_t) *p1 == on_failure_jump
6788 && (re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == start_memory
6789 && p1[2+OFFSET_ADDRESS_SIZE] == *p)
6791 /* If this group ever matched anything, then restore
6792 what its registers were before trying this last
6793 failed match, e.g., with `(a*)*b' against `ab' for
6794 regstart[1], and, e.g., with `((a*)*(b*)*)*'
6795 against `aba' for regend[3].
6797 Also restore the registers for inner groups for,
6798 e.g., `((a*)(b*))*' against `aba' (register 3 would
6799 otherwise get trashed). */
6801 if (EVER_MATCHED_SOMETHING (reg_info[*p]))
6805 EVER_MATCHED_SOMETHING (reg_info[*p]) = 0;
6807 /* Restore this and inner groups' (if any) registers. */
6808 for (r = *p; r < (unsigned) *p + (unsigned) *(p + 1);
6811 regstart[r] = old_regstart[r];
6813 /* xx why this test? */
6814 if (old_regend[r] >= regstart[r])
6815 regend[r] = old_regend[r];
6819 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
6820 PUSH_FAILURE_POINT (p1 + mcnt, d, -2);
6826 /* Move past the register number and the inner group count. */
6831 /* \<digit> has been turned into a `duplicate' command which is
6832 followed by the numeric value of <digit> as the register number. */
6835 register const CHAR_T *d2, *dend2;
6836 int regno = *p++; /* Get which register to match against. */
6837 DEBUG_PRINT2 ("EXECUTING duplicate %d.\n", regno);
6839 /* Can't back reference a group which we've never matched. */
6840 if (REG_UNSET (regstart[regno]) || REG_UNSET (regend[regno]))
6843 /* Where in input to try to start matching. */
6844 d2 = regstart[regno];
6846 /* Where to stop matching; if both the place to start and
6847 the place to stop matching are in the same string, then
6848 set to the place to stop, otherwise, for now have to use
6849 the end of the first string. */
6851 dend2 = ((FIRST_STRING_P (regstart[regno])
6852 == FIRST_STRING_P (regend[regno]))
6853 ? regend[regno] : end_match_1);
6856 /* If necessary, advance to next segment in register
6860 if (dend2 == end_match_2) break;
6861 if (dend2 == regend[regno]) break;
6863 /* End of string1 => advance to string2. */
6865 dend2 = regend[regno];
6867 /* At end of register contents => success */
6868 if (d2 == dend2) break;
6870 /* If necessary, advance to next segment in data. */
6873 /* How many characters left in this segment to match. */
6876 /* Want how many consecutive characters we can match in
6877 one shot, so, if necessary, adjust the count. */
6878 if (mcnt > dend2 - d2)
6881 /* Compare that many; failure if mismatch, else move
6884 ? PREFIX(bcmp_translate) (d, d2, mcnt, translate)
6885 : memcmp (d, d2, mcnt*sizeof(UCHAR_T)))
6887 d += mcnt, d2 += mcnt;
6889 /* Do this because we've match some characters. */
6890 SET_REGS_MATCHED ();
6896 /* begline matches the empty string at the beginning of the string
6897 (unless `not_bol' is set in `bufp'), and, if
6898 `newline_anchor' is set, after newlines. */
6900 DEBUG_PRINT1 ("EXECUTING begline.\n");
6902 if (AT_STRINGS_BEG (d))
6909 else if (d[-1] == '\n' && bufp->newline_anchor)
6913 /* In all other cases, we fail. */
6917 /* endline is the dual of begline. */
6919 DEBUG_PRINT1 ("EXECUTING endline.\n");
6921 if (AT_STRINGS_END (d))
6929 /* We have to ``prefetch'' the next character. */
6930 else if ((d == end1 ? *string2 : *d) == '\n'
6931 && bufp->newline_anchor)
6938 /* Match at the very beginning of the data. */
6940 DEBUG_PRINT1 ("EXECUTING begbuf.\n");
6941 if (AT_STRINGS_BEG (d))
6948 /* Match at the very end of the data. */
6950 DEBUG_PRINT1 ("EXECUTING endbuf.\n");
6951 if (AT_STRINGS_END (d))
6958 /* on_failure_keep_string_jump is used to optimize `.*\n'. It
6959 pushes NULL as the value for the string on the stack. Then
6960 `pop_failure_point' will keep the current value for the
6961 string, instead of restoring it. To see why, consider
6962 matching `foo\nbar' against `.*\n'. The .* matches the foo;
6963 then the . fails against the \n. But the next thing we want
6964 to do is match the \n against the \n; if we restored the
6965 string value, we would be back at the foo.
6967 Because this is used only in specific cases, we don't need to
6968 check all the things that `on_failure_jump' does, to make
6969 sure the right things get saved on the stack. Hence we don't
6970 share its code. The only reason to push anything on the
6971 stack at all is that otherwise we would have to change
6972 `anychar's code to do something besides goto fail in this
6973 case; that seems worse than this. */
6974 CASE (on_failure_keep_string_jump):
6975 DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump");
6977 EXTRACT_NUMBER_AND_INCR (mcnt, p);
6979 DEBUG_PRINT3 (" %d (to %p):\n", mcnt, p + mcnt);
6981 DEBUG_PRINT3 (" %d (to 0x%x):\n", mcnt, p + mcnt);
6984 PUSH_FAILURE_POINT (p + mcnt, NULL, -2);
6988 /* Uses of on_failure_jump:
6990 Each alternative starts with an on_failure_jump that points
6991 to the beginning of the next alternative. Each alternative
6992 except the last ends with a jump that in effect jumps past
6993 the rest of the alternatives. (They really jump to the
6994 ending jump of the following alternative, because tensioning
6995 these jumps is a hassle.)
6997 Repeats start with an on_failure_jump that points past both
6998 the repetition text and either the following jump or
6999 pop_failure_jump back to this on_failure_jump. */
7000 CASE (on_failure_jump):
7002 DEBUG_PRINT1 ("EXECUTING on_failure_jump");
7004 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7006 DEBUG_PRINT3 (" %d (to %p)", mcnt, p + mcnt);
7008 DEBUG_PRINT3 (" %d (to 0x%x)", mcnt, p + mcnt);
7011 /* If this on_failure_jump comes right before a group (i.e.,
7012 the original * applied to a group), save the information
7013 for that group and all inner ones, so that if we fail back
7014 to this point, the group's information will be correct.
7015 For example, in \(a*\)*\1, we need the preceding group,
7016 and in \(zz\(a*\)b*\)\2, we need the inner group. */
7018 /* We can't use `p' to check ahead because we push
7019 a failure point to `p + mcnt' after we do this. */
7022 /* We need to skip no_op's before we look for the
7023 start_memory in case this on_failure_jump is happening as
7024 the result of a completed succeed_n, as in \(a\)\{1,3\}b\1
7026 while (p1 < pend && (re_opcode_t) *p1 == no_op)
7029 if (p1 < pend && (re_opcode_t) *p1 == start_memory)
7031 /* We have a new highest active register now. This will
7032 get reset at the start_memory we are about to get to,
7033 but we will have saved all the registers relevant to
7034 this repetition op, as described above. */
7035 highest_active_reg = *(p1 + 1) + *(p1 + 2);
7036 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
7037 lowest_active_reg = *(p1 + 1);
7040 DEBUG_PRINT1 (":\n");
7041 PUSH_FAILURE_POINT (p + mcnt, d, -2);
7045 /* A smart repeat ends with `maybe_pop_jump'.
7046 We change it to either `pop_failure_jump' or `jump'. */
7047 CASE (maybe_pop_jump):
7048 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7049 DEBUG_PRINT2 ("EXECUTING maybe_pop_jump %d.\n", mcnt);
7051 register UCHAR_T *p2 = p;
7053 /* Compare the beginning of the repeat with what in the
7054 pattern follows its end. If we can establish that there
7055 is nothing that they would both match, i.e., that we
7056 would have to backtrack because of (as in, e.g., `a*a')
7057 then we can change to pop_failure_jump, because we'll
7058 never have to backtrack.
7060 This is not true in the case of alternatives: in
7061 `(a|ab)*' we do need to backtrack to the `ab' alternative
7062 (e.g., if the string was `ab'). But instead of trying to
7063 detect that here, the alternative has put on a dummy
7064 failure point which is what we will end up popping. */
7066 /* Skip over open/close-group commands.
7067 If what follows this loop is a ...+ construct,
7068 look at what begins its body, since we will have to
7069 match at least one of that. */
7073 && ((re_opcode_t) *p2 == stop_memory
7074 || (re_opcode_t) *p2 == start_memory))
7076 else if (p2 + 2 + 2 * OFFSET_ADDRESS_SIZE < pend
7077 && (re_opcode_t) *p2 == dummy_failure_jump)
7078 p2 += 2 + 2 * OFFSET_ADDRESS_SIZE;
7084 /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
7085 to the `maybe_finalize_jump' of this case. Examine what
7088 /* If we're at the end of the pattern, we can change. */
7091 /* Consider what happens when matching ":\(.*\)"
7092 against ":/". I don't really understand this code
7094 p[-(1+OFFSET_ADDRESS_SIZE)] = (UCHAR_T)
7097 (" End of pattern: change to `pop_failure_jump'.\n");
7100 else if ((re_opcode_t) *p2 == exactn
7102 || (re_opcode_t) *p2 == exactn_bin
7104 || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
7107 = *p2 == (UCHAR_T) endline ? '\n' : p2[2];
7109 if (((re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == exactn
7111 || (re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == exactn_bin
7113 ) && p1[3+OFFSET_ADDRESS_SIZE] != c)
7115 p[-(1+OFFSET_ADDRESS_SIZE)] = (UCHAR_T)
7118 DEBUG_PRINT3 (" %C != %C => pop_failure_jump.\n",
7120 (wint_t) p1[3+OFFSET_ADDRESS_SIZE]);
7122 DEBUG_PRINT3 (" %c != %c => pop_failure_jump.\n",
7124 (char) p1[3+OFFSET_ADDRESS_SIZE]);
7129 else if ((re_opcode_t) p1[3] == charset
7130 || (re_opcode_t) p1[3] == charset_not)
7132 int negate = (re_opcode_t) p1[3] == charset_not;
7134 if (c < (unsigned) (p1[4] * BYTEWIDTH)
7135 && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
7138 /* `negate' is equal to 1 if c would match, which means
7139 that we can't change to pop_failure_jump. */
7142 p[-3] = (unsigned char) pop_failure_jump;
7143 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7146 #endif /* not WCHAR */
7149 else if ((re_opcode_t) *p2 == charset)
7151 /* We win if the first character of the loop is not part
7153 if ((re_opcode_t) p1[3] == exactn
7154 && ! ((int) p2[1] * BYTEWIDTH > (int) p1[5]
7155 && (p2[2 + p1[5] / BYTEWIDTH]
7156 & (1 << (p1[5] % BYTEWIDTH)))))
7158 p[-3] = (unsigned char) pop_failure_jump;
7159 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7162 else if ((re_opcode_t) p1[3] == charset_not)
7165 /* We win if the charset_not inside the loop
7166 lists every character listed in the charset after. */
7167 for (idx = 0; idx < (int) p2[1]; idx++)
7168 if (! (p2[2 + idx] == 0
7169 || (idx < (int) p1[4]
7170 && ((p2[2 + idx] & ~ p1[5 + idx]) == 0))))
7175 p[-3] = (unsigned char) pop_failure_jump;
7176 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7179 else if ((re_opcode_t) p1[3] == charset)
7182 /* We win if the charset inside the loop
7183 has no overlap with the one after the loop. */
7185 idx < (int) p2[1] && idx < (int) p1[4];
7187 if ((p2[2 + idx] & p1[5 + idx]) != 0)
7190 if (idx == p2[1] || idx == p1[4])
7192 p[-3] = (unsigned char) pop_failure_jump;
7193 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7197 #endif /* not WCHAR */
7199 p -= OFFSET_ADDRESS_SIZE; /* Point at relative address again. */
7200 if ((re_opcode_t) p[-1] != pop_failure_jump)
7202 p[-1] = (UCHAR_T) jump;
7203 DEBUG_PRINT1 (" Match => jump.\n");
7204 goto unconditional_jump;
7206 /* Note fall through. */
7209 /* The end of a simple repeat has a pop_failure_jump back to
7210 its matching on_failure_jump, where the latter will push a
7211 failure point. The pop_failure_jump takes off failure
7212 points put on by this pop_failure_jump's matching
7213 on_failure_jump; we got through the pattern to here from the
7214 matching on_failure_jump, so didn't fail. */
7215 CASE (pop_failure_jump):
7217 /* We need to pass separate storage for the lowest and
7218 highest registers, even though we don't care about the
7219 actual values. Otherwise, we will restore only one
7220 register from the stack, since lowest will == highest in
7221 `pop_failure_point'. */
7222 active_reg_t dummy_low_reg, dummy_high_reg;
7223 UCHAR_T *pdummy = NULL;
7224 const CHAR_T *sdummy = NULL;
7226 DEBUG_PRINT1 ("EXECUTING pop_failure_jump.\n");
7227 POP_FAILURE_POINT (sdummy, pdummy,
7228 dummy_low_reg, dummy_high_reg,
7229 reg_dummy, reg_dummy, reg_info_dummy);
7231 /* Note fall through. */
7235 DEBUG_PRINT2 ("\n%p: ", p);
7237 DEBUG_PRINT2 ("\n0x%x: ", p);
7239 /* Note fall through. */
7241 /* Unconditionally jump (without popping any failure points). */
7243 EXTRACT_NUMBER_AND_INCR (mcnt, p); /* Get the amount to jump. */
7244 DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt);
7245 p += mcnt; /* Do the jump. */
7247 DEBUG_PRINT2 ("(to %p).\n", p);
7249 DEBUG_PRINT2 ("(to 0x%x).\n", p);
7254 /* We need this opcode so we can detect where alternatives end
7255 in `group_match_null_string_p' et al. */
7256 CASE (jump_past_alt):
7257 DEBUG_PRINT1 ("EXECUTING jump_past_alt.\n");
7258 goto unconditional_jump;
7261 /* Normally, the on_failure_jump pushes a failure point, which
7262 then gets popped at pop_failure_jump. We will end up at
7263 pop_failure_jump, also, and with a pattern of, say, `a+', we
7264 are skipping over the on_failure_jump, so we have to push
7265 something meaningless for pop_failure_jump to pop. */
7266 CASE (dummy_failure_jump):
7267 DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n");
7268 /* It doesn't matter what we push for the string here. What
7269 the code at `fail' tests is the value for the pattern. */
7270 PUSH_FAILURE_POINT (NULL, NULL, -2);
7271 goto unconditional_jump;
7274 /* At the end of an alternative, we need to push a dummy failure
7275 point in case we are followed by a `pop_failure_jump', because
7276 we don't want the failure point for the alternative to be
7277 popped. For example, matching `(a|ab)*' against `aab'
7278 requires that we match the `ab' alternative. */
7279 CASE (push_dummy_failure):
7280 DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n");
7281 /* See comments just above at `dummy_failure_jump' about the
7283 PUSH_FAILURE_POINT (NULL, NULL, -2);
7286 /* Have to succeed matching what follows at least n times.
7287 After that, handle like `on_failure_jump'. */
7289 EXTRACT_NUMBER (mcnt, p + OFFSET_ADDRESS_SIZE);
7290 DEBUG_PRINT2 ("EXECUTING succeed_n %d.\n", mcnt);
7293 /* Originally, this is how many times we HAVE to succeed. */
7297 p += OFFSET_ADDRESS_SIZE;
7298 STORE_NUMBER_AND_INCR (p, mcnt);
7300 DEBUG_PRINT3 (" Setting %p to %d.\n", p - OFFSET_ADDRESS_SIZE
7303 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p - OFFSET_ADDRESS_SIZE
7310 DEBUG_PRINT2 (" Setting two bytes from %p to no_op.\n",
7311 p + OFFSET_ADDRESS_SIZE);
7313 DEBUG_PRINT2 (" Setting two bytes from 0x%x to no_op.\n",
7314 p + OFFSET_ADDRESS_SIZE);
7318 p[1] = (UCHAR_T) no_op;
7320 p[2] = (UCHAR_T) no_op;
7321 p[3] = (UCHAR_T) no_op;
7328 EXTRACT_NUMBER (mcnt, p + OFFSET_ADDRESS_SIZE);
7329 DEBUG_PRINT2 ("EXECUTING jump_n %d.\n", mcnt);
7331 /* Originally, this is how many times we CAN jump. */
7335 STORE_NUMBER (p + OFFSET_ADDRESS_SIZE, mcnt);
7338 DEBUG_PRINT3 (" Setting %p to %d.\n", p + OFFSET_ADDRESS_SIZE,
7341 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p + OFFSET_ADDRESS_SIZE,
7344 goto unconditional_jump;
7346 /* If don't have to jump any more, skip over the rest of command. */
7348 p += 2 * OFFSET_ADDRESS_SIZE;
7351 CASE (set_number_at):
7353 DEBUG_PRINT1 ("EXECUTING set_number_at.\n");
7355 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7357 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7359 DEBUG_PRINT3 (" Setting %p to %d.\n", p1, mcnt);
7361 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p1, mcnt);
7363 STORE_NUMBER (p1, mcnt);
7368 /* The DEC Alpha C compiler 3.x generates incorrect code for the
7369 test WORDCHAR_P (d - 1) != WORDCHAR_P (d) in the expansion of
7370 AT_WORD_BOUNDARY, so this code is disabled. Expanding the
7371 macro and introducing temporary variables works around the bug. */
7374 DEBUG_PRINT1 ("EXECUTING wordbound.\n");
7375 if (AT_WORD_BOUNDARY (d))
7381 CASE (notwordbound):
7382 DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
7383 if (AT_WORD_BOUNDARY (d))
7389 boolean prevchar, thischar;
7391 DEBUG_PRINT1 ("EXECUTING wordbound.\n");
7392 if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
7397 prevchar = WORDCHAR_P (d - 1);
7398 thischar = WORDCHAR_P (d);
7399 if (prevchar != thischar)
7406 CASE (notwordbound):
7408 boolean prevchar, thischar;
7410 DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
7411 if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
7414 prevchar = WORDCHAR_P (d - 1);
7415 thischar = WORDCHAR_P (d);
7416 if (prevchar != thischar)
7423 DEBUG_PRINT1 ("EXECUTING wordbeg.\n");
7424 if (!AT_STRINGS_END (d) && WORDCHAR_P (d)
7425 && (AT_STRINGS_BEG (d) || !WORDCHAR_P (d - 1)))
7432 DEBUG_PRINT1 ("EXECUTING wordend.\n");
7433 if (!AT_STRINGS_BEG (d) && WORDCHAR_P (d - 1)
7434 && (AT_STRINGS_END (d) || !WORDCHAR_P (d)))
7442 DEBUG_PRINT1 ("EXECUTING before_dot.\n");
7443 if (PTR_CHAR_POS ((unsigned char *) d) >= point)
7448 DEBUG_PRINT1 ("EXECUTING at_dot.\n");
7449 if (PTR_CHAR_POS ((unsigned char *) d) != point)
7454 DEBUG_PRINT1 ("EXECUTING after_dot.\n");
7455 if (PTR_CHAR_POS ((unsigned char *) d) <= point)
7460 DEBUG_PRINT2 ("EXECUTING syntaxspec %d.\n", mcnt);
7465 DEBUG_PRINT1 ("EXECUTING Emacs wordchar.\n");
7469 /* Can't use *d++ here; SYNTAX may be an unsafe macro. */
7471 if (SYNTAX (d[-1]) != (enum syntaxcode) mcnt)
7473 SET_REGS_MATCHED ();
7476 CASE (notsyntaxspec):
7477 DEBUG_PRINT2 ("EXECUTING notsyntaxspec %d.\n", mcnt);
7479 goto matchnotsyntax;
7482 DEBUG_PRINT1 ("EXECUTING Emacs notwordchar.\n");
7486 /* Can't use *d++ here; SYNTAX may be an unsafe macro. */
7488 if (SYNTAX (d[-1]) == (enum syntaxcode) mcnt)
7490 SET_REGS_MATCHED ();
7493 #else /* not emacs */
7495 DEBUG_PRINT1 ("EXECUTING non-Emacs wordchar.\n");
7497 if (!WORDCHAR_P (d))
7499 SET_REGS_MATCHED ();
7504 DEBUG_PRINT1 ("EXECUTING non-Emacs notwordchar.\n");
7508 SET_REGS_MATCHED ();
7511 #endif /* not emacs */
7517 continue; /* Successfully executed one pattern command; keep going. */
7521 /* We goto here if a matching operation fails. */
7523 if (!FAIL_STACK_EMPTY ())
7524 { /* A restart point is known. Restore to that state. */
7525 DEBUG_PRINT1 ("\nFAIL:\n");
7526 POP_FAILURE_POINT (d, p,
7527 lowest_active_reg, highest_active_reg,
7528 regstart, regend, reg_info);
7530 /* If this failure point is a dummy, try the next one. */
7534 /* If we failed to the end of the pattern, don't examine *p. */
7538 boolean is_a_jump_n = false;
7540 /* If failed to a backwards jump that's part of a repetition
7541 loop, need to pop this failure point and use the next one. */
7542 switch ((re_opcode_t) *p)
7546 case maybe_pop_jump:
7547 case pop_failure_jump:
7550 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7553 if ((is_a_jump_n && (re_opcode_t) *p1 == succeed_n)
7555 && (re_opcode_t) *p1 == on_failure_jump))
7563 if (d >= string1 && d <= end1)
7567 break; /* Matching at this starting point really fails. */
7571 goto restore_best_regs;
7575 return -1; /* Failure to match. */
7578 /* Subroutine definitions for re_match_2. */
7581 /* We are passed P pointing to a register number after a start_memory.
7583 Return true if the pattern up to the corresponding stop_memory can
7584 match the empty string, and false otherwise.
7586 If we find the matching stop_memory, sets P to point to one past its number.
7587 Otherwise, sets P to an undefined byte less than or equal to END.
7589 We don't handle duplicates properly (yet). */
7592 PREFIX(group_match_null_string_p) (UCHAR_T **p, UCHAR_T *end,
7593 PREFIX(register_info_type) *reg_info)
7596 /* Point to after the args to the start_memory. */
7597 UCHAR_T *p1 = *p + 2;
7601 /* Skip over opcodes that can match nothing, and return true or
7602 false, as appropriate, when we get to one that can't, or to the
7603 matching stop_memory. */
7605 switch ((re_opcode_t) *p1)
7607 /* Could be either a loop or a series of alternatives. */
7608 case on_failure_jump:
7610 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7612 /* If the next operation is not a jump backwards in the
7617 /* Go through the on_failure_jumps of the alternatives,
7618 seeing if any of the alternatives cannot match nothing.
7619 The last alternative starts with only a jump,
7620 whereas the rest start with on_failure_jump and end
7621 with a jump, e.g., here is the pattern for `a|b|c':
7623 /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
7624 /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
7627 So, we have to first go through the first (n-1)
7628 alternatives and then deal with the last one separately. */
7631 /* Deal with the first (n-1) alternatives, which start
7632 with an on_failure_jump (see above) that jumps to right
7633 past a jump_past_alt. */
7635 while ((re_opcode_t) p1[mcnt-(1+OFFSET_ADDRESS_SIZE)] ==
7638 /* `mcnt' holds how many bytes long the alternative
7639 is, including the ending `jump_past_alt' and
7642 if (!PREFIX(alt_match_null_string_p) (p1, p1 + mcnt -
7643 (1 + OFFSET_ADDRESS_SIZE),
7647 /* Move to right after this alternative, including the
7651 /* Break if it's the beginning of an n-th alternative
7652 that doesn't begin with an on_failure_jump. */
7653 if ((re_opcode_t) *p1 != on_failure_jump)
7656 /* Still have to check that it's not an n-th
7657 alternative that starts with an on_failure_jump. */
7659 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7660 if ((re_opcode_t) p1[mcnt-(1+OFFSET_ADDRESS_SIZE)] !=
7663 /* Get to the beginning of the n-th alternative. */
7664 p1 -= 1 + OFFSET_ADDRESS_SIZE;
7669 /* Deal with the last alternative: go back and get number
7670 of the `jump_past_alt' just before it. `mcnt' contains
7671 the length of the alternative. */
7672 EXTRACT_NUMBER (mcnt, p1 - OFFSET_ADDRESS_SIZE);
7674 if (!PREFIX(alt_match_null_string_p) (p1, p1 + mcnt, reg_info))
7677 p1 += mcnt; /* Get past the n-th alternative. */
7683 assert (p1[1] == **p);
7689 if (!PREFIX(common_op_match_null_string_p) (&p1, end, reg_info))
7692 } /* while p1 < end */
7695 } /* group_match_null_string_p */
7698 /* Similar to group_match_null_string_p, but doesn't deal with alternatives:
7699 It expects P to be the first byte of a single alternative and END one
7700 byte past the last. The alternative can contain groups. */
7703 PREFIX(alt_match_null_string_p) (UCHAR_T *p, UCHAR_T *end,
7704 PREFIX(register_info_type) *reg_info)
7711 /* Skip over opcodes that can match nothing, and break when we get
7712 to one that can't. */
7714 switch ((re_opcode_t) *p1)
7717 case on_failure_jump:
7719 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7724 if (!PREFIX(common_op_match_null_string_p) (&p1, end, reg_info))
7727 } /* while p1 < end */
7730 } /* alt_match_null_string_p */
7733 /* Deals with the ops common to group_match_null_string_p and
7734 alt_match_null_string_p.
7736 Sets P to one after the op and its arguments, if any. */
7739 PREFIX(common_op_match_null_string_p) (UCHAR_T **p, UCHAR_T *end,
7740 PREFIX(register_info_type) *reg_info)
7747 switch ((re_opcode_t) *p1++)
7767 assert (reg_no > 0 && reg_no <= MAX_REGNUM);
7768 ret = PREFIX(group_match_null_string_p) (&p1, end, reg_info);
7770 /* Have to set this here in case we're checking a group which
7771 contains a group and a back reference to it. */
7773 if (REG_MATCH_NULL_STRING_P (reg_info[reg_no]) == MATCH_NULL_UNSET_VALUE)
7774 REG_MATCH_NULL_STRING_P (reg_info[reg_no]) = ret;
7780 /* If this is an optimized succeed_n for zero times, make the jump. */
7782 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7790 /* Get to the number of times to succeed. */
7791 p1 += OFFSET_ADDRESS_SIZE;
7792 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7796 p1 -= 2 * OFFSET_ADDRESS_SIZE;
7797 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7805 if (!REG_MATCH_NULL_STRING_P (reg_info[*p1]))
7810 p1 += 2 * OFFSET_ADDRESS_SIZE;
7813 /* All other opcodes mean we cannot match the empty string. */
7819 } /* common_op_match_null_string_p */
7822 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
7823 bytes; nonzero otherwise. */
7826 PREFIX(bcmp_translate) (const CHAR_T *s1, const CHAR_T *s2,
7828 RE_TRANSLATE_TYPE translate)
7830 register const UCHAR_T *p1 = (const UCHAR_T *) s1;
7831 register const UCHAR_T *p2 = (const UCHAR_T *) s2;
7835 if (((*p1<=0xff)?translate[*p1++]:*p1++)
7836 != ((*p2<=0xff)?translate[*p2++]:*p2++))
7839 if (translate[*p1++] != translate[*p2++]) return 1;
7847 #else /* not INSIDE_RECURSION */
7849 /* Entry points for GNU code. */
7851 /* re_compile_pattern is the GNU regular expression compiler: it
7852 compiles PATTERN (of length SIZE) and puts the result in BUFP.
7853 Returns 0 if the pattern was valid, otherwise an error string.
7855 Assumes the `allocated' (and perhaps `buffer') and `translate' fields
7856 are set in BUFP on entry.
7858 We call regex_compile to do the actual compilation. */
7861 re_compile_pattern (const char *pattern,
7863 struct re_pattern_buffer *bufp)
7867 /* GNU code is written to assume at least RE_NREGS registers will be set
7868 (and at least one extra will be -1). */
7869 bufp->regs_allocated = REGS_UNALLOCATED;
7871 /* And GNU code determines whether or not to get register information
7872 by passing null for the REGS argument to re_match, etc., not by
7876 /* Match anchors at newline. */
7877 bufp->newline_anchor = 1;
7880 if (MB_CUR_MAX != 1)
7881 ret = wcs_regex_compile (pattern, length, re_syntax_options, bufp);
7884 ret = byte_regex_compile (pattern, length, re_syntax_options, bufp);
7888 return gettext (re_error_msgid + re_error_msgid_idx[(int) ret]);
7891 weak_alias (__re_compile_pattern, re_compile_pattern)
7894 /* Entry points compatible with 4.2 BSD regex library. We don't define
7895 them unless specifically requested. */
7897 #if defined _REGEX_RE_COMP || defined _LIBC
7899 /* BSD has one and only one pattern buffer. */
7900 static struct re_pattern_buffer re_comp_buf;
7904 /* Make these definitions weak in libc, so POSIX programs can redefine
7905 these names if they don't use our functions, and still use
7906 regcomp/regexec below without link errors. */
7909 re_comp (const char *s)
7915 if (!re_comp_buf.buffer)
7916 return (char *) gettext ("No previous regular expression");
7920 if (!re_comp_buf.buffer)
7922 re_comp_buf.buffer = malloc (200);
7923 if (re_comp_buf.buffer == NULL)
7924 return (char *) gettext (re_error_msgid
7925 + re_error_msgid_idx[(int) REG_ESPACE]);
7926 re_comp_buf.allocated = 200;
7928 re_comp_buf.fastmap = malloc (1 << BYTEWIDTH);
7929 if (re_comp_buf.fastmap == NULL)
7930 return (char *) gettext (re_error_msgid
7931 + re_error_msgid_idx[(int) REG_ESPACE]);
7934 /* Since `re_exec' always passes NULL for the `regs' argument, we
7935 don't need to initialize the pattern buffer fields which affect it. */
7937 /* Match anchors at newlines. */
7938 re_comp_buf.newline_anchor = 1;
7941 if (MB_CUR_MAX != 1)
7942 ret = wcs_regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
7945 ret = byte_regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
7950 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
7951 return (char *) gettext (re_error_msgid + re_error_msgid_idx[(int) ret]);
7959 re_exec (const char *s)
7961 const int len = strlen (s);
7963 0 <= re_search (&re_comp_buf, s, len, 0, len, 0);
7966 #endif /* _REGEX_RE_COMP */
7968 /* POSIX.2 functions. Don't define these for Emacs. */
7972 /* regcomp takes a regular expression as a string and compiles it.
7974 PREG is a regex_t *. We do not expect any fields to be initialized,
7975 since POSIX says we shouldn't. Thus, we set
7977 `buffer' to the compiled pattern;
7978 `used' to the length of the compiled pattern;
7979 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
7980 REG_EXTENDED bit in CFLAGS is set; otherwise, to
7981 RE_SYNTAX_POSIX_BASIC;
7982 `newline_anchor' to REG_NEWLINE being set in CFLAGS;
7983 `fastmap' to an allocated space for the fastmap;
7984 `fastmap_accurate' to zero;
7985 `re_nsub' to the number of subexpressions in PATTERN.
7987 PATTERN is the address of the pattern string.
7989 CFLAGS is a series of bits which affect compilation.
7991 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
7992 use POSIX basic syntax.
7994 If REG_NEWLINE is set, then . and [^...] don't match newline.
7995 Also, regexec will try a match beginning after every newline.
7997 If REG_ICASE is set, then we considers upper- and lowercase
7998 versions of letters to be equivalent when matching.
8000 If REG_NOSUB is set, then when PREG is passed to regexec, that
8001 routine will report only success or failure, and nothing about the
8004 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
8005 the return codes and their meanings.) */
8008 regcomp (regex_t *preg, const char *pattern, int cflags)
8012 = (cflags & REG_EXTENDED) ?
8013 RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC;
8015 /* regex_compile will allocate the space for the compiled pattern. */
8017 preg->allocated = 0;
8020 /* Try to allocate space for the fastmap. */
8021 preg->fastmap = (char *) malloc (1 << BYTEWIDTH);
8023 if (cflags & REG_ICASE)
8029 malloc (CHAR_SET_SIZE * sizeof (*(RE_TRANSLATE_TYPE)0));
8030 if (preg->translate == NULL)
8031 return (int) REG_ESPACE;
8033 /* Map uppercase characters to corresponding lowercase ones. */
8034 for (i = 0; i < CHAR_SET_SIZE; i++)
8035 preg->translate[i] = ISUPPER (i) ? TOLOWER (i) : i;
8038 preg->translate = NULL;
8040 /* If REG_NEWLINE is set, newlines are treated differently. */
8041 if (cflags & REG_NEWLINE)
8042 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
8043 syntax &= ~RE_DOT_NEWLINE;
8044 syntax |= RE_HAT_LISTS_NOT_NEWLINE;
8045 /* It also changes the matching behavior. */
8046 preg->newline_anchor = 1;
8049 preg->newline_anchor = 0;
8051 preg->no_sub = !!(cflags & REG_NOSUB);
8053 /* POSIX says a null character in the pattern terminates it, so we
8054 can use strlen here in compiling the pattern. */
8056 if (MB_CUR_MAX != 1)
8057 ret = wcs_regex_compile (pattern, strlen (pattern), syntax, preg);
8060 ret = byte_regex_compile (pattern, strlen (pattern), syntax, preg);
8062 /* POSIX doesn't distinguish between an unmatched open-group and an
8063 unmatched close-group: both are REG_EPAREN. */
8064 if (ret == REG_ERPAREN) ret = REG_EPAREN;
8066 if (ret == REG_NOERROR && preg->fastmap)
8068 /* Compute the fastmap now, since regexec cannot modify the pattern
8070 if (re_compile_fastmap (preg) == -2)
8072 /* Some error occurred while computing the fastmap, just forget
8074 free (preg->fastmap);
8075 preg->fastmap = NULL;
8082 weak_alias (__regcomp, regcomp)
8086 /* regexec searches for a given pattern, specified by PREG, in the
8089 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
8090 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
8091 least NMATCH elements, and we set them to the offsets of the
8092 corresponding matched substrings.
8094 EFLAGS specifies `execution flags' which affect matching: if
8095 REG_NOTBOL is set, then ^ does not match at the beginning of the
8096 string; if REG_NOTEOL is set, then $ does not match at the end.
8098 We return 0 if we find a match and REG_NOMATCH if not. */
8101 regexec (const regex_t *preg, const char *string,
8102 size_t nmatch, regmatch_t pmatch[], int eflags)
8105 struct re_registers regs;
8106 regex_t private_preg;
8107 int len = strlen (string);
8108 boolean want_reg_info = !preg->no_sub && nmatch > 0;
8110 private_preg = *preg;
8112 private_preg.not_bol = !!(eflags & REG_NOTBOL);
8113 private_preg.not_eol = !!(eflags & REG_NOTEOL);
8115 /* The user has told us exactly how many registers to return
8116 information about, via `nmatch'. We have to pass that on to the
8117 matching routines. */
8118 private_preg.regs_allocated = REGS_FIXED;
8122 regs.num_regs = nmatch;
8123 regs.start = TALLOC (nmatch * 2, regoff_t);
8124 if (regs.start == NULL)
8125 return (int) REG_NOMATCH;
8126 regs.end = regs.start + nmatch;
8129 /* Perform the searching operation. */
8130 ret = re_search (&private_preg, string, len,
8131 /* start: */ 0, /* range: */ len,
8132 want_reg_info ? ®s : 0);
8134 /* Copy the register information to the POSIX structure. */
8141 for (r = 0; r < nmatch; r++)
8143 pmatch[r].rm_so = regs.start[r];
8144 pmatch[r].rm_eo = regs.end[r];
8148 /* If we needed the temporary register info, free the space now. */
8152 /* We want zero return to mean success, unlike `re_search'. */
8153 return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH;
8156 weak_alias (__regexec, regexec)
8160 /* Returns a message corresponding to an error code, ERRCODE, returned
8161 from either regcomp or regexec. We don't use PREG here. */
8164 regerror (int errcode, const regex_t *preg, char *errbuf, size_t errbuf_size)
8170 || errcode >= (int) (sizeof (re_error_msgid_idx)
8171 / sizeof (re_error_msgid_idx[0])))
8172 /* Only error codes returned by the rest of the code should be passed
8173 to this routine. If we are given anything else, or if other regex
8174 code generates an invalid error code, then the program has a bug.
8175 Dump core so we can fix it. */
8178 msg = gettext (re_error_msgid + re_error_msgid_idx[errcode]);
8180 msg_size = strlen (msg) + 1; /* Includes the null. */
8182 if (errbuf_size != 0)
8184 if (msg_size > errbuf_size)
8186 #if defined HAVE_MEMPCPY || defined _LIBC
8187 *((char *) __mempcpy (errbuf, msg, errbuf_size - 1)) = '\0';
8189 memcpy (errbuf, msg, errbuf_size - 1);
8190 errbuf[errbuf_size - 1] = 0;
8194 memcpy (errbuf, msg, msg_size);
8200 weak_alias (__regerror, regerror)
8204 /* Free dynamically allocated space used by PREG. */
8207 regfree (regex_t *preg)
8209 if (preg->buffer != NULL)
8210 free (preg->buffer);
8211 preg->buffer = NULL;
8213 preg->allocated = 0;
8216 if (preg->fastmap != NULL)
8217 free (preg->fastmap);
8218 preg->fastmap = NULL;
8219 preg->fastmap_accurate = 0;
8221 if (preg->translate != NULL)
8222 free (preg->translate);
8223 preg->translate = NULL;
8226 weak_alias (__regfree, regfree)
8229 #endif /* not emacs */
8231 #endif /* not INSIDE_RECURSION */
8235 #undef STORE_NUMBER_AND_INCR
8236 #undef EXTRACT_NUMBER
8237 #undef EXTRACT_NUMBER_AND_INCR
8239 #undef DEBUG_PRINT_COMPILED_PATTERN
8240 #undef DEBUG_PRINT_DOUBLE_STRING
8242 #undef INIT_FAIL_STACK
8243 #undef RESET_FAIL_STACK
8244 #undef DOUBLE_FAIL_STACK
8245 #undef PUSH_PATTERN_OP
8246 #undef PUSH_FAILURE_POINTER
8247 #undef PUSH_FAILURE_INT
8248 #undef PUSH_FAILURE_ELT
8249 #undef POP_FAILURE_POINTER
8250 #undef POP_FAILURE_INT
8251 #undef POP_FAILURE_ELT
8254 #undef PUSH_FAILURE_POINT
8255 #undef POP_FAILURE_POINT
8257 #undef REG_UNSET_VALUE
8265 #undef INIT_BUF_SIZE
8266 #undef GET_BUFFER_SPACE
8274 #undef EXTEND_BUFFER
8275 #undef GET_UNSIGNED_NUMBER
8276 #undef FREE_STACK_RETURN
8278 # undef POINTER_TO_OFFSET
8279 # undef MATCHING_IN_FRST_STRING
8281 # undef AT_STRINGS_BEG
8282 # undef AT_STRINGS_END
8285 # undef FREE_VARIABLES
8286 # undef NO_HIGHEST_ACTIVE_REG
8287 # undef NO_LOWEST_ACTIVE_REG
8291 # undef COMPILED_BUFFER_VAR
8292 # undef OFFSET_ADDRESS_SIZE
8293 # undef CHAR_CLASS_SIZE
8300 # define DEFINED_ONCE